\documentclass[magisterska]{pracamgr}

\usepackage{amsfonts, amsmath, amsthm}

\usepackage[polish]{babel} \usepackage[MeX]{polski} \usepackage[utf8]{inputenc}

\usepackage[pdftex]{graphicx}
\usepackage{color}
\usepackage{wrapfig}
\usepackage{subfig}
\usepackage{float}
\usepackage{rotating}

\RequirePackage[active]{srcltx}

\newcommand{\note}[1]{\textbf{\textcolor{red}{#1}}}

\newcommand{\mas}[1]{\textit{#1}}

\newcommand{\vb}[1]{\texttt{#1}}

\newcommand{\dir}[1]{\vspace{0.5cm}\noindent\large{\textit{#1}}\newline}

\newcommand{\script}[1]{\vspace{0.5cm}\noindent\large{\vb{#1}}\newline}

\newenvironment{citeenv}
{\vspace{5pt}\begin{center} \begin{minipage}{0.9\textwidth} \begin{it}}
{\end{it} \end{minipage} \end{center} \vspace{5pt}}

\newenvironment{commentenv}
{\vspace{5pt}\begin{center} \begin{minipage}{0.9\textwidth} \begin{it} \textbf{Uwaga.}} {\end{it} \end{minipage}
\end{center} \vspace{5pt}}

\newenvironment{definitionenv}
{\vspace{5pt}\begin{center} \begin{minipage}{0.9\textwidth} \begin{it} \textbf{Definicja.}} {\end{it} \end{minipage}
\end{center} \vspace{5pt}}

\newenvironment{factenv}
{\vspace{5pt}\begin{center} \begin{minipage}{0.9\textwidth} \begin{it} \textbf{Fakt.}} {\end{it} \end{minipage}
\end{center} \vspace{5pt}}

% mmatczuk \author{Michał Matczuk} \nralbumu{222102}

\author{Filip Grządkowski, Michał Matczuk}
\nralbumu{219446, 222102}

\title{Platforma do wizualizacji systemów wieloagentowych w środowisku 3D}
\tytulang{Platform for multiagent systems visualization in 3D}
\kierunek{Informatyka}
\zakres{systemów wieloagentowych}
\opiekun{dr. hab. Barbary Dunin-Kęplicz}
\date{Wrzesień 2009}

\dziedzina{Systemy wieloagentowe}
\klasyfikacja{I.2.11 Multiagent systems}

\keywords{Multiagent systems, JADE, OpenGL}

\begin{document}
\maketitle

\begin{abstract}
Systemy wieloagentowe odgrywają coraz większą rolę w informatyce zarówno teoretycznej jak i praktycznej. 
Wizualizacja pozwala na bardziej efektywne analizowanie działania systemów, może też być dobrym narzędziem dydaktycznym.
Praca ta ma na celu stworzenie łatwego w obsłudze silnika do wizualizacji agentów (robotów) w środowisku 3D. 
Jej integralną częścią jest autorski edytor do tworzenia powierzchni w trzech wymiarach wykorzystujący płaty Bezier.
Jako przykład zastosowania został zrealizowany i opisany system wieloagentowny służący do schwytania uciekiniera z zoo.
Rozważany problem został po raz pierwszy postawiony w instytucie Informatyki na wydziale MIMUW w ramach przedmiotu ``Modelowanie współpracy w systemach wieloagentowych''.

\end{abstract}

\tableofcontents

\chapter*{Wprowadzenie}
% to napiszemy na samym KOŃCU
% \begin{itemize}
%  \item tematem pracy jest wizualizacja 3D systemu wieloagentowego oraz rozwiązanie przykładowego problemu mas
%  \item platforma może służyć do innych implementacji ze względu na separacje modułów i funkcjonalne API
%  \item problemy, które można wizualizować naszymi narzędziami są bardzo szerokie i jest to pierwsze takie narzędzie dostępne w Polsce (? skąd to wiadomo?)
%  \item symulujemy działanie prawdziwych robotów - prosty model fizyczny (niemożna przechodzić przez ziemie, niemożna stać w tym samym miejscu, są ograniczenia prędkości etc)
% \end{itemize}

Tematem niniejszej pracy jest platforma wizualizacji systemów wieloagentowych w środowisku 3D. Opisywane narzędzie autorzy
wykorzystali do rozwiązania przykładowego problemu opisanego w części \ref{part:mas}.

Dokładny opis algorytmów, struktur danych oraz diagramów klas pozwala zrozumieć zasadę działania programu.
Dzięki wyraźnej separacji modułów oraz dokładnemu opisowi API (``Dokumentacja javadoc'') możliwe jest
łatwe wykorzystanie platformy do wizualizacji dowolnego systemu, bez konieczności zagłębiania się w szczegóły implementacyjne.
Takie rozwiązanie pozwala w wygodny sposób analizować skuteczność algorytmów z dziedziny MAS.

Platforma w swoich założeniach symuluje działanie prawdziwych robotów. Domyślny model świata implementuje podstawowe pojęcia fizyczne
znane z rzeczywistości (grawitacja, ruch, konflikty pozycji etc). Program pozwala jednak na stosunkowo dużą
dowolność programisty, pozostawiając mu możliwość konfiguracji prawie każdego elementu.
Dzięki elastycznej konstrukcji wykorzystującej dziedziczenie, możliwe jest zdefiniowanie własnych, dowolnych reguł, co
dodatkowo poszerza spektrum zastosowań.

\part{Platforma wizualizacyjna}\label{part:platform}

% \begin{itemize}
%  \item platforma pozwala na wizualizacje powierzani 3D w wygodny sposób
%  \item jest zintegrowana ze środowiskiem MAS
%  \item dodatkowo pozwala na modelowanie powierzchni do symulacji (plansz / map)
%  \item w samym symulatorze mamy wygodne opcje do sprawdzania stanu agentów, debugowania ich zachowania, analizowania komunikacji etc
%  \item jest to dedykowane narzędzie do wizualizacji
%  \item na razie nie ma takiego narzędzia powszechnie dostępnego
%  \item dzięki temu, ze je piszemy studenci kolejnych lat będą mogli w przystępny sposób analizować działanie ich implementacji mas (w 3D)
% \end{itemize}
% 
% Podstawowym celem działania platformy jest wizualizacja powierzchni 2D oraz 3D wraz agentami,
% oraz umożliwienie łatwego manipulowania całym środowiskiem. Dzieki implementacji podstawowych klas
% stworzenie 


\chapter{Struktura rozwiązania}
Platforma wizualizacyjna, będąca przedmiotem tej pracy, składa się z pięciu głównych elementów, zwanych
komponentami. W ramach rozwiązania zostały zaimplementowane dwie aplikacje i trzy pomocnicze biblioteki. W pracy tej
będziemy omawiać zastosowane rozwiązania, zależności między komponentami i ich architekturę.
\newline

Nazwy komponentów, zgodnie z konwencją, zostały poprzedzone przedrostkiem ``mas''.
Poniższa tabela przedstawia ich skrótowy podział ze względu na rolę.

\vspace{0.5cm}
\begin{tabular}{ r c l }
mas-commons & - & biblioteka zawierająca podstawowe definicje (takie jak np. mapa) \\
& & używane przez wszystkie pozostałe komponenty \\
mas-visualization & - & biblioteka implementująca API wizualizacji, odpowiedzialna \\
& & za renderowanie scen \\
mas-core & - & główna biblioteka integrująca system wieloagentowy JADE \\
& & z komponentem wizualizacyjnym mas-visualization\\
mas-deerhunter & - & przykładowa aplikacja wieloagentowa (opis w części II) \\
& & korzystająca z komponentu mas-core do wizualizacji\\
mas-mapeditor & - & edytor map, zaimplementowany w celu ułatwienia rysowania \\
& & plansz (środowisk) dla systemów wieloagentowych \\
\end{tabular}
\vspace{0.5cm}

Całe rozwiązanie zostało zaimplementowane w języku Java. Do budowania projektu wykorzystane
zostało narzędzie maven.
Poza standardowymi bibliotekami Javy rozwiązanie wymaga poniższych bibliotek zewnętrznych:

\vspace{0.5cm}
\begin{tabular}{ r c l }
SLF4J & - & wygodna i konfigurowalna biblioteka służąca do logowania zdarzeń\\
& & [http://www.slf4j.org]\\
JUnit & - & biblioteka ułatwiająca testy jednostkowe [http://www.junit.org/]\\
SWT & - & biblioteka służąca do rysowania okienek [http://www.eclipse.org/swt/]\\
JOGL  & - & biblioteka do obsługi grafiki 3D, adapter dla systemu OpenGL\\
& & zrealizowany poprzez wywołania JNI [https://jogl.dev.java.net]\\
JADE & - & biblioteka implementująca agentów, ich zachowania i komunikację,\\
& & w pełni zgodna ze standardem FIPA [http://jade.tilab.com]\\
\end{tabular}
\vspace{0.5cm}

Wszystkie wymagane biblioteki, które nie mogą być ściągnięte automatycznie podczas kompilacji znajdują się na płycie CD
dołączonej do pracy; więcej o bibliotekach w podrozdziale \ref{section:budowanie}.
\newline
\newline
Przeanalizujmy zależności między komponentami z uwzględnieniem bibliotek zewnętrznych. Ponieważ prezentowane
rozwiązanie składa się z dwóch aplikacji: edytora plansz (mas-mapeditor) oraz przykładowej
wizualizacji (mas-deerhunter). Pokażemy je z tych dwóch perspektyw.

\vspace{0.5cm}
\begin{figure}[H]
\centering
\includegraphics[width=15cm]{images/dependencydeerhunter.png}
\caption{Zależności między komponentami z perspektywy mas-deerhunter}
\label{fig:dependencydeerhunter}
\end{figure}
\vspace{0.5cm}

Komponent mas-deerhunter jest aplikacją wieloagentową stworzoną celem sprawdzenia użyteczności
rozwiązań wizualizacyjnych zaimplementowanych w komponencie mas-core. Część \ref{part:mas} pracy zawiera opis problemu
wieloagentowego i jego rozwiązania zaimplementowanego w mas-deerhunter. Komponent jest zależny tylko od głównej
biblioteki pozwalającej na wizualizację: mas-core.

Komponent mas-core jest najbardziej istotnym elementem całego rozwiązania. Tu znajduje się warstwa integrująca pozostałe
komponenty z platformą wieloagentową JADE. Sukces integracji polega na stworzeniu agentów kompatybilnych z JADE, którzy
potrafią posługiwać się zrobionymi wcześniej komponentami wizualizacyjnymi. Jak łatwo zauważyć mas-core zależy od
biblioteki mas-commons, zawierającej podstawowe definicje, biblioteki mas-visualization, odpowiedzialnej za renderowanie
scen 3D oraz od platformy wieloagentowej JADE.

Komponent wizualizacyjny mas-visualization, odpowiedzialny za renderowanie scen 3D, korzysta z biblioteki JOGL, zapewniającej dostęp do
interface'u OpenGL z poziomu Javy. Wszystkie komponenty wypisują komunikaty o stanie aplikacji i/lub zdarzeniach
korzystając z biblioteki SLF4J. Dzięki takiemu rozwiązaniu można w łatwy sposób filtrować komunikaty wypisywane
przez program, zmieniać ich format oraz miejsce, do którego są one zapisywane. Wykorzystana przez na implementacja
fasady SLF4J to Log4j.
% \newpage

\begin{figure}[H]
\centering
\includegraphics[width=15cm]{images/dependencymapeditor.png}
\caption{Zależności między komponentami z perspektywy mas-mapeditor}
\label{fig:dependencymapeditor}
\end{figure}

Komponent mas-mapeditor jest odpowiedzialny za modelowanie powierzchni. Wygodny interfejs pozwala użytkownikowi 
zmieniać rozmiar oraz kształt mapy. Do generowania okien i ich elementów, edytor wykorzystuje bibliotekę SWT.
Podobnie jak w pozostałych komponentach, tak i tu za wizualizację odpowiada komponent mas-visualization.

\section{Struktura katalogów}
W tym rozdziale opiszemy strukturę projektu ze względu na fizyczne rozmieszczenie plików i katalogów. Jest to
niezbędna wiedza w przypadku budowania własnej aplikacji MAS, uruchomienia przykładów, czy przejrzenia kodu źródłowego.
Struktura katalogów na dołączonej płycie CD oraz na stronie projektu:\newline
http://code.google.com/p/deerhunter/source/browse/\#svn/trunk
jest analogiczna.
\newline
\newline
Poniżej przedstawiamy zawartość głównego katalogu.
\begin{verbatim}
drwx------ 9 user group  142 2009-05-31 09:41 CODE
drwx------ 4 user group   73 2009-05-20 00:17 DOCS
drwx------ 3 user group   87 2009-03-08 10:13 MAPS
drwx------ 6 user group  155 2009-03-02 14:52 REPO
-rw------- 1 user group  368 2009-03-02 14:52 README
-rwx------ 1 user group  628 2009-03-16 20:16 build.sh
-rwx------ 1 user group  406 2009-03-02 23:12 count.sh
-rwx------ 1 user group 1690 2009-05-07 22:23 deployrepo.sh
-rwx------ 1 user group  325 2009-03-02 23:14 genjavadoc.sh
-rwx------ 1 user group  312 2009-03-05 13:54 runjade.sh
\end{verbatim}

\dir{CODE} Katalog zawierający pliki źródłowe wszystkich komponentów zaimplementowanych w ramach pracy. Struktura tego
katalogu zawiera po jednym podkatalogu na komponent oraz główny deskryptor projektu \vb{pom.xml}, wymagany przez system
budowania aplikacji maven, używany w tej pracy (więcej o budowaniu aplikacji w \ref{section:budowanie}).
\newline
\newline
Poniżej przedstawiamy zawartość katalogu \vb{CODE}.

\begin{verbatim}
drwx------ 6 user group  102 2009-05-31 09:41 mas-commons
drwx------ 6 user group  156 2009-05-31 10:17 mas-core
drwx------ 6 user group  156 2009-06-12 13:37 mas-deerhunter
drwx------ 6 user group  102 2009-05-31 09:41 mas-mapeditor
drwx------ 6 user group  102 2009-05-31 10:17 mas-visualization
-rw------- 1 user group 1445 2009-03-14 10:27 pom.xml
\end{verbatim}

Struktura wewnętrzna komponentów jest domyślną strukturą systemu maven. Więcej na ten temat można znaleźć na
stronie [http://maven.apache.org/guides/introduction/\newline introduction-to-the-standard-directory-layout.html].
Każdy komponent ma swój deskryptor (plik \vb{pom.xml} w katalogu komponentu) oraz podfolder \vb{src} ze źródłami.
\newline
\newline
Poniżej przedstawiamy zawartość katalogu \vb{CODE/mas-core}.

\begin{verbatim}
drwx------ 5 user group   39 2009-03-08 16:22 src
-rw------- 1 user group 2050 2009-03-14 13:01 pom.xml
\end{verbatim}

Katalog \vb{scr} ma dwa podkatalogi: \vb{main} (główne źródła) oraz \vb{test} (źródła testów).
Podczas kompilacji do formatu \vb{jar} pliki z katalogu \vb{test} są pomijane.

Struktura wewnętrzna katalogu głównego jak i testowego są identyczne. W katalogu \vb{main} znajduje się
jeden podkatalog: \vb{java} a w nim pliki źródłowe \vb{*.java} pogrupowane w podkatalogach według przestrzeni nazw, w
których się znajdują. Dokładniej, każdy znak ``\vb{.}'' w przestrzeni nazw tłumaczony jest na przejście o jeden poziom w dół w
strukturze katalogów. Na przykład klasa \vb{pl.edu.mimuw.mas.agent.Visualization3DAgent} znajduje się w pliku
\vb{CODE/mas-core/src/main/java/pl/edu/mimuw/mas/agent/}
\newline
\vb{Visualization3DAgent.java}.

\dir{DOCS} Katalog zawierający dokumentację projektu. Dokumentacja techniczna (opis klas i funkcjonalności
wygenerowany z komentarzy w źródłach) znajduje się w podkatalogu \vb{javadocs}. Ponadto załączona jest wersja
elektroniczna niniejszego dokumentu w piku \vb{mgr.pdf} jak i jego źródła \LaTeX wraz ze wszystkimi potrzebnymi do
kompilacji elementami w podkatalogu \vb{mas-mgr}.
\newline
\newline
Poniżej przedstawiamy zawartość katalogu \vb{DOCS}.

\begin{verbatim}
drwxr-xr-x 5 user group   4096 2009-06-13 12:49 javadocs
drwx------ 5 user group     94 2009-06-13 12:46 mas-mgr
-rw-r--r-- 1 user group 696036 2009-06-13 12:13 mgr.pdf
\end{verbatim}

\dir{MAPS} Katalog zwierający plansze wygenerowane przez autorów za pomocą edytora map.

\dir{REPO} Katalog zawierający biblioteki wymagane przez aplikację, których system budowania maven nie jest w stanie
ściągnąć automatycznie podczas kompilacji. W podkatalogach mamy trzy biblioteki: JADE w wersji 3.6.1, JOGL w wersji 1.1.1 oraz SWT w wersji 3.4.
W celu ułatwienia procesu instalacji można wykorzystać przygotowany skrypt instalacyjny (więcej o instalacji bibliotek w rozdziale
\ref{section:budowanie}).
\newline
\newline
Poniżej przedstawiamy zawartość katalogu \vb{REPO}.

\begin{verbatim}
drwx------ 4 user group 102 2009-03-02 23:51 jade-3.6.1
drwx------ 5 user group  74 2009-03-02 14:49 jogl-1.1.1
drwx------ 5 user group  76 2009-03-02 14:47 swt-3.4
\end{verbatim}

\vspace{1cm}

W głównym katalogu znajdują się także (oprócz podkatalogów opisanych powyżej) skrypty które zostały napisane w celu
ułatwienia pracy i automatyzacji często wykonywanych czynności. Opis tych skryptów i przykłady ich użycia znajdują się
w następnym rozdziale.

\section{Budowanie i uruchamianie aplikacji}\label{section:budowanie}
Jednym z założeń tego projektu była łatwość jego kompilacji ze źródeł. W konsekwencji nie
udostępniamy wersji binarnych, a szereg skryptów mających ułatwiać budowanie i
uruchamianie.

\subsection*{Wymagania wstępne}
Nasz projekt, jako że jest napisany w Javie, można uruchomić na dowolnej architekturze i pod dowolnym
systemem operacyjnym, pod warunkiem posiadania wirtualnej maszyny Javy i zainstalowania wszystkich wymaganych
bibliotek.

Skrypty budujące dostarczane wraz ze źródłami mają jednak bardziej rygorystyczne założenia:

\begin{enumerate}
 \item system operacyjne z rodziny UNIX/Linux
 \item architektura x86(32 bitowa) i x86\_64 (64 bitowa);
\end{enumerate}

\begin{commentenv}
W przypadku ręcznego instalowania bibliotek należy zadbać o ich wersje (JADE v.3.6.1, JOGL v.1.1.1, SWT v.3.4),
oraz docelowy system operacyjny i architekturę.
\end{commentenv}
\newpage
Poza wymienionymi wcześniej ograniczeniami do kompilacji i/lub działania komponentów potrzebne są następujące
elementy:
\begin{enumerate}
 \item Java SE 6 lub nowsza
 \item Narzędzie maven2
 \item Powłoka systemowa bash
 \item Komenda \vb{sudo}
 \item Implementacja OpenGL (np. libgl-mesa-dri);
\end{enumerate}

\subsection*{Skrypty}

\script{deployrepo.sh}
Skrypt instalacyjny; instaluje potrzebne biblioteki (z katalogu \vb{REPO}), których nie ma w oficjalnych repozytoriach
maven'a. Skrypt przyjmuje jeden parametr określający architekturę (\vb{x\_86} lub \vb{x\_86\_64}).
Wywołanie bez parametru spowoduje wyświetlenie pomocy.

\begin{verbatim}
user@localhost:~/project/mas$ ./deployrepo.sh
--- USE: deployrepo.sh {x86 | x86_64}
\end{verbatim}

Użytkownik musi być wpisany do konfiguracji systemowej jako \vb{sudoer} i w tym trybie mieć uprawnienia zapisu w katalogu /usr/lib.

Pomyślne wywołanie rozpoczyna procedurę instalacyjną, na końcu której skrypt prosi o podanie hasła użytkownika, celem przejścia w tryb
super użytkownika (\vb{sudo})
\begin{verbatim}
user@localhost:~/project/mas$ ./deployrepo.sh x86_64
.
.
.
--- feed /usr/lib
[sudo] password for user:
\end{verbatim}

\script{build.sh}
Skrypt budujący; buduje i jeśli budowanie zakończyło się pomyślnie uruchamia \mas{cel}. Skrypt przyjmuje od jednego do
trzech parametrów. Wywołanie bez parametru spowoduje wyświetlenie pomocy.

\begin{verbatim}
user@localhost:~/project/mas$ ./build.sh
--- USE: build.sh {mapeditor | deerhunter} [clean, online]
\end{verbatim}

Pierwszy parametr to \mas{cel} do zbudowania: \vb{mapeditor} oznacza chęć uruchomienia komponentu mas-mapeditor,
\vb{deerhunter} zaś komponentu mas-deerhunter. Ustawienie flagi \vb{clean} spowoduje przebudowanie całości
(dokładniej wyczyszczenie pamięci podręcznej skompilowanych klas i ich budowę na nowo). Ustawienie flagi \vb{online}
uruchomi maven'a w taki sposób by próbował ściągać wymagane biblioteki z internetu, w przypadku ich braku w lokalnym
repozytorium. Pierwsze uruchomienie skryptu powinno odbyć się z flagą \vb{online}, celem instalacji brakujących
biblioteki. Należy pamiętać o konieczności uruchomienia skryptu \vb{deployrepo.sh} przed pierwszym uruchomieniem
skryptu budującego.

\script{genjavadoc.sh}
Skrypt dokumentujący; generuje dokumentację (tzw. javadoc) z komentarzy w kodzie dla wszystkich modułów. W efekcie
produkuje stronę internetową (zobacz rys. \ref{fig:javadoc}) z opisem klas pakietów etc. Wynik zapisywany jest w katalogu
\vb{CODE/target/site/apidocs}.

\begin{figure}[H]
\centering
\includegraphics[width=14.65cm]{images/javadoc_small.png}
\caption{Dokumentacja javadoc}
\label{fig:javadoc}
\end{figure}

\script{count.sh}
Skrypt liczący liczbę linii w plikach \vb{*.java}.

\begin{verbatim}
user@localhost:~/project/mas$ ./count.sh
/home/user/project/mas/CODE/mas-commons: 706
/home/user/project/mas/CODE/mas-core: 2773
/home/user/project/mas/CODE/mas-deerhunter: 3927
/home/user/project/mas/CODE/mas-mapeditor: 1947
/home/user/project/mas/CODE/mas-visualization: 1568

total: 10900
\end{verbatim}

\script{runjade.sh}
Skrypt uruchamiający platformę JADE, aktualnie nie jest już używany.

\chapter{Edytor map (mas-mapeditor)}

Edytor map jest graficznym narzędziem do tworzenia wirtualnej przestrzeni imitującej rzeczywistość, w której zostają osadzeni agenci
celem wykonania zleconych zadań. Dzięki zastosowanym modelom matematycznym (patrz \ref{platy}) wygenerowany świat wystarcza do
realnej analizy skuteczności zastosowanych algorytmów w systemie wieloagentowym.

\section{Modelowanie powierzchni}

Podstawowymi założeniami do sposobu modelowania powierzchni, postawionymi przez autorów, były:
\begin{itemize}
 \item dobre odwzorowanie rzeczywistych powierzchni
 \item wygoda manipulacji
 \item szybkość działania (przy rozmiarze planszy 1500x1500 lub mniejszej)
 \item łatwość implementacji
\end{itemize}
Najlepszym kandydatem okazały się płaty Bezier'a będące rodzajem funkcji sklejanej odwzorowującej powierzchnie gładkie.
Dzięki zastosowaniu autorskiego algorytmu udało się zachować łatwość implementacji, przy jego minimalnym koszcie obliczeniowym
(patrz \ref{algorytm}).

\subsection{Płaty Bezier'a}\label{platy}
% \begin{itemize}
%  \item wprowadzenie
%  \item definicje
%  \item punkty kontrolne
%  \item wzorek 2D
%  \item uogólnienie 3D
% \end{itemize}

Płaty Bezier'a (rzadziej płaty tensorowe) są rodzajem funkcji sklejanej rzutującej kwadrat jednostkowy na przestrzeń k-wymiarową:
$$[0,1]\times[0,1]\rightarrow R^k$$

Kształt powierzchni stopnia $(n,m)$ jest zdefiniowany, podobnie jak dla krzywych Bezier'a, przez zbiór $(n+1)(m+1)$ punktów kontrolnych $k_{ij}$,
które dla wygody są często zapisywane w dwuwymiarowej tablicy - $p_{i,j}$ to punkt w i-tej kolumnie i w j-tym wierszu.
Opisywana powierzchnia jest tego samego stopnia co punkty kontrolne.

Analogicznie do łamanej kontrolnej dla krzywej, dla płatów używa się określenia siatki kontrolnej, którą jest zbiór linii łączących sąsiednie punkty kontrolne (sąsiednie, czyli $p_{ij}\mapsto p_{i(j + 1)}$, albo $p_{ij}\mapsto p_{(i+1)j}$).

Łamana, której wierzchołkami są punkty kontrolne o stałym indeksie $i$ nazywana jest kolumną, o stałym indeksie $j$ wierszem.

\noindent Dowolny punkt na powierzchni oblicza się zgodnie ze wzorem:\nopagebreak

$$p(u,v) = \sum^n_{i=0} \sum^m_{j=0} p_{ij} B^n_i(u)B^m_j(v),~dla~u,v\in[0,1]$$

\noindent $B^n_i(u),B^m_j(v)$ to wielomiany bazowe Bernsteina zdefiniowane:
$$B^n_i(t)=\binom{n}{i}t^i(1-t)^{n-i},~dla~i=0..n$$

Jako ciekawostkę warto nadmienić, że funkcje te zostały po raz pierwszy opisane w 1972 roku przez francuskiego inżyniera Pierre'a Bezier.
Pierwotnie miały służyć do projektowania nadwozi samochodów. Obecnie krzywe i płaty Bezier'a są szeroko rozpowszechnione w grafice komputerowej
ze względu na ich kompaktowość oraz łatwość manipulacji.

\subsection{Algorytm}\label{algorytm}
% \begin{itemize}
%  \item obliczanie wprost z definicji
%  \item mozna duzo zapamietywac
%  \item zlozonosc obliczniowa i pamieciowa (jest ok przy ograniczeniach na rozmiar)
%  \item pseudokod
% \end{itemize}

\noindent W praktyce obliczenie punktu $p(u,v)$ przeprowadza się zgodnie ze wzorem:

\begin{equation}\label{eq:main}
p(u,v) = \sum^n_{i=0} B^n_i(u) \left( \sum^m_{j=0} p_{ij} B^m_j(v) \right),~dla~u,v\in[0,1]
\end{equation}
lub
\begin{equation}
p(u,v) = \sum^m_{j=0} B^m_j(v) \left( \sum^n_{i=0} p_{ij} B^n_i(u) \right),~dla~u,v\in[0,1]
\end{equation}

\noindent Bez straty ogólności, w dalszych rozważaniach możemy zająć się tylko wzorem \ref{eq:main}
\newline
\newline
Przeanalizujmy złożoność algorytmu obliczającego wartość jednego punktu przy bezpośrednim zastosowaniu
wzoru \ref{eq:main}.
\newline\newline
Złożoność poszczególnych elementów:
\begin{itemize}
\item $x_n$ - $\theta(log(n))$
\item $\binom{n}{k}$ - $\theta(log(k))$
\end{itemize}

Zatem koszt całego algorytmu $T(n,m)$:
$$T(n,m) = \sum^n_{i=0} (log(i) + log(n)) \left( \sum^m_{j=0} (log(j) + log(m) \right) = $$
$$ = \sum^n_{i=0} (log(i) + log(n)) \left( \sum^m_{j=0}log(j) + mlog(m) \right) = $$
$$ = nlog(n) \left( \sum^m_{j=0}log(j) + mlog(m) \right) +  \sum^n_{i=0} log(i) \left( \sum^m_{j=0}log(j) + mlog(m) \right) = $$
$$ = \theta\left( nlog(n) \left( \sum^m_{j=0}log(j) + mlog(m) \right) \right) = \theta(nlog(n)m(log(m))$$

Przyjmując jako reprezentację planszy tablicę punktów o wymiarach $k\times j$ (kolumny $\times$ wiersze), aby wyznaczyć kształt całej planszy
musimy wykonać $\theta(kjnmlog(n)log(m))$ operacji. Przy obranych przez nas założeniach na rozmiar planszy (1500x1500)
oraz rozmiar siatki kontrolnej (20x20), otrzymujemy $\sim 1,5 \times 10^9$ operacji. Jest to czas zdecydowanie za duży,
bowiem na większości domowych komputerów wykonywać się będzie około 1 sek.
\newline
\newline
Przy kolejnych iteracjach zauważamy, że wiele obliczeń jest powtarzanych. Dla przykładu, przy każdej kolejnej iteracji
po wierszu obliczamy zawsze wszystkie Symbole Newtona.

Rozwijając pomysł zapamiętywania danych, możemy na początku obliczyć dla każdego wiersza wartość wielomianu bazowego Bernsteina
dla wszystkich możliwych wartości pierwszej współrzędnej. Podobnie tablicujemy wartość wyrażenia $\sum^m_{j=0} p_{ij} B^m_j(v)$
dla każdej kolumny i każdej możliwej wartości drugiego argumentu. Jest to możliwe, bo argumenty funkcji $p$ są ograniczone
do punktów na planszy (ze względu reprezentację tablicową).

\noindent Ostatecznie otrzymujemy następujący algorytm (zapisany w pseudokodzie):

\begin{enumerate}
 
 \item Obliczenie wartości wielomianu bazowego Bernsteina dla wierszy
 
\begin{verbatim}
binomial = 0
m = len(rows)
for row in rows do
   binomial = next_binomial(binomial)
   j = nr(row)
   for y_value in y_values do:
      bernstein = binomial * pow(y_value, m) * pow(y_value * (m - j))
      bernstein_row[row][y_value] = bernstein
   done
done
\end{verbatim}

\item Obliczenie wartości wielomianu bazowego Bernsteina dla kolumn

\begin{verbatim}
binomial = 0
n = len(columns)
for col in columns do
   binomial = next_binomial(binomial)
   i = nr(col)
   for x_value in x_values do:
      bernstein = binomial * pow(x_value, n) * pow(x_value * (n - i))
      berstein_col[col][x_value] = bernstein
   done
done
\end{verbatim}

\item Obliczenie wartości wyrażenia $\sum^m_{j=0} p_{ij} B^m_j(v)$ dla kolumn

\begin{verbatim}
k = get_control_points()
for y_value in y_values do:
   for col in columns do:
      row_sum[col][y_value] = 0
      for row in rows do:
         bernstein = berstein_row[row][y_value]
         row_sum[col][y_value] += bernstein * k[col][row]
      done
   done
done
\end{verbatim}

\item Obliczenie wartości funkcji dla punktu $(u,v)$

\begin{verbatim}
value = 0
x_value = get_x_value()
y_value = get_y_value()
for col in cols do:
   value += bernstein_col[col][x_value] * row_sum[col][y_value]
done
\end{verbatim}
\end{enumerate}

\noindent Warto zauważyć, że przy wielokrotnym obliczaniu kształtu planszy przy wykorzystaniu powyższego algorytmu wystarczy powtórzyć jedynie
dwa ostatnie kroki. Pozostałe są bowiem niezależne od samej siatki kontrolnej.
\newline

\noindent Przeanalizujmy koszt czasowy każdego z kroków algorytmu:

\begin{enumerate}
 \item Obliczenie wartości wielomianu bazowego Bernsteina dla wierszy\newline
 koszt wykonania \vb{next\_binomial} $O(1)$\newline
 koszt obliczenia wartości \vb{bernstein} $O(log(m))$\newline
 \textbf{koszt całkowity} $O(mjlog(m))$\newline
 
 \item Obliczenie wartości wielomianu bazowego Bernsteina dla kolumn\newline
 koszt wykonania \vb{next\_binomial} $O(1)$\newline
 koszt obliczenia wartości \vb{bernstein} $O(log(n))$\newline
 \textbf{koszt całkowity} $O(nklog(n))$\newline
 
 \item\label{alg:krok3} Obliczenie wartości wyrażenia $\sum^m_{j=0} p_{ij} B^m_j(v)$ dla kolumn\newline
 \textbf{koszt całkowity} $O(jnm)$\newline
 
 \item Obliczenie wartości funkcji dla punktu $(u,v)$\newline
 \textbf{koszt całkowity} $O(n)$\newline
 
\end{enumerate}

Jak widać przeważającym krokiem jest krok \ref{alg:krok3}. Możemy więc stwierdzić, że \textbf{koszt całkowity algorytmu} to $O(jnm)$.
Dla nałożonych ograniczeń rozmiaru planszy ($1500\times 1500$) i siatki ($20\times 20$) otrzymujemy $\sim0,6\times10^6$ operacji.
Po przyspieszeniach otrzymaliśmy więc rozwiązanie szybsze o kilka rzędów wielkości (dla przypomnienia poprzednio\newline\
$O(kjnmlog(n)log(m))$).
\newline
\newline
Wraz z ograniczeniem kosztu czasowego wzrósł koszt pamięciowy:
\begin{itemize}
 \item \vb{bernstein\_row} - $O(mj)$
 \item \vb{bernstein\_col} - $O(nk)$
 \item \vb{row\_sum} - $O(nj)$
\end{itemize}
Jest to jednak koszt akceptowalny przy nałożonych ograniczeniach.

\subsection{Implementacja}
% \begin{itemize}
%  \item użyte obiekty (Chart, Area, ControlPoints)
%  \item czemu akurat Bezier
%  \item czemu wdzieliśmy równe siatki kontrolne
%  \item czemu akurat takie ograniczenia rozmiarów
%  \item opis implementacji
% \end{itemize}

\subsubsection{Definicje obiektów}

\begin{itemize}
 \item \textbf{Chart}
 \begin{verbatim}
/**
* Główny obiekt reprezentujący powierzchnię.
*/
public class Chart implements Serializable {
  /* metody statyczne */
  public static boolean isOnChart(int x, int y, int columns,
    int rows);

  /* prywatne zmienne */
  private static final float defaultDistance = 1.0f;
  private float[][] grid;
  private float distance;
  private int columns, rows;

  /* konstruktory */
  public Chart(int columns, int rows, float distance);
  public Chart(int columns, int rows);
  public Chart(int columns, int rows, float distance,
    float[][] grid);
  public Chart(int columns, int rows, float[][] grid);

  /* gettery i settery */
  public int getColumnsCount();
  public int getRowsCount();
  public float getDistance();
  public float getHeight(int column, int row);
  public synchronized void setHeight(int col, int row,
    float height);
  public synchronized void setColumnHeight(int column,
    float[] data);
  public synchronized void setRowHeight(int row, float[] data);
  public String getInfo();

  /* pozostałe metody */
  public boolean isOnChart(int x, int y);
}
\end{verbatim}

\item \textbf{Area}\newline
\begin{verbatim}
/**
* Obszar ograniczony prostokątem
*/
public class Area {
  /* metody statyczne */
  public static boolean checkArea(int x_0, int y_0, int x_1,
    int y_1)

  /* prywatne zmienne */
  private final int[] area;

  /* konstruktor */
  public Area(int x_0, int y_0, int x_1, int y_1)
    throws WrongAreaException;

  /* gettery i setter */
  public int[] getArea();
}
\end{verbatim}

\item \textbf{ControlPoints}\newline
\begin{verbatim}
/**
* Siatka punktów kontrolnych powierchni Beziera
*/
public class ControlPoints implements Serializable {
  /* prywatne zmienne */
  private boolean[][] activeNodes;
  private float[][] grid;
  private float columns;
  private float rows;
  private Area area;

  /* konstruktor */
  public ControlPoints(int columns, int rows, Area area);

  /* gettery i settery */
  public boolean isSelected(int col, int row);
  public float getHeight(int col, int row);
  public void setHeight(int col, int row, float hgt);
  public void shiftSelectedHeight(float shift);
  public Area getArea();
  public float getColumnsCount();
  public float getRowsCount();
  public String getInfo();

  /* pozostałe metody */
  public void select(int col, int row);
  public void unselect(int col, int row);
  public void toggle(int col, int row);
  public void selectNone();
}
\end{verbatim}

\end{itemize}

% \newpage
\section{Współpraca użytkownika z programem}
% \begin{itemize}
%  \item jak używać programu mas-mapeditor
%  \item dostępne opcje (siatki, zoom, menu) opis - screeny
%  \item tutorial jak zrobić jakąś powierzchnie; poobracać etc\ldots
% \end{itemize}

\subsection{Opis funkcjonalności}

\subsubsection{Tworzenie nowej mapy}

% \begin{wrapfigure}{r}{5cm}
% \centering
% \vspace{-20pt}
% \includegraphics{images/new_map.png}
% \caption{Tworzenie nowej mapy}
% \label{fig:new_map}
% \end{wrapfigure}

Stworzenie nowej mapy jest możliwe poprzez wybór odpowiedniej opcji w menu ``Plik'' (patrz \ref{fig:new_map}).
Następnie użytkownik jest proszony o podanie liczby kolumn, wierszy i odległości pomiędzy punktami
nowo tworzonej mapy (\ref{fig:new_map_dialog}), która po zaakceptowaniu konfiguracji jest wyświetlana
w oknie wizualizacji.

\begin{figure}[H]
\centering
\subfloat[Element menu]{\label{fig:new_map}\includegraphics{images/new_map.png}}
\hspace{3cm}
\subfloat[Okno dialogowe]{\label{fig:new_map_dialog}\includegraphics{images/new_map_dialog.png}}
\caption{Tworzenie nowej mapy}
\end{figure}

\subsubsection{Zapisywanie mapy pod nową nazwą (``Zapisz jako'')}


\parbox[t][5cm][t]{1.0\textwidth}{

\begin{wrapfigure}{r}{5cm}
\centering
\vspace{-20pt}
\includegraphics{images/save_as.png}
\caption{Zapisywanie mapy pod nową nazwą}
\label{fig:save_as}
\end{wrapfigure}

Zapisanie mapy pod nową nazwą (również w przypadku pierwszego zapisu) jest możliwe poprzez wybór
odpowiedniej opcji w menu ``Plik'' (\ref{fig:save_as}). Następnie użytkownik jest proszony o podanie
ścieżki wskazującej miejsce zapisu.
}

\subsubsection{Zapisywanie mapy do bieżącego pliku (``Zapisz'')}

\parbox[t][5cm][t]{1.0\textwidth}{

\begin{wrapfigure}{r}{6cm}
\centering
\vspace{-20pt}
\includegraphics{images/save.png}
\caption{Zapisywanie mapy do bieżącego pliku}
\label{fig:save}
\end{wrapfigure}

Zapisanie mapy do bieżącego pliku jest możliwe poprzez wybór odpowiedniej opcji w menu ``Plik''
(\ref{fig:save}). Opcja ta jest dostępna tylko po wcześniejszym zapisie pod nową nazwą lub otwarciu
zapisanej mapy.
}

\subsubsection{Otwieranie zapisanej mapy}

\parbox[t][5cm][t]{1.0\textwidth}{

\begin{wrapfigure}{r}{5cm}
\centering
\vspace{-20pt}
\includegraphics{images/open_map.png}
\caption{Otwieranie zapisanej mapy}
\label{fig:open}
\end{wrapfigure}

Zapisanie mapy pod nową nazwą (również w przypadku pierwszego zapisu) jest możliwe poprzez wybór
odpowiedniej opcji w menu ``Plik'' (\ref{fig:open}). Następnie użytkownik jest proszony o podanie
ścieżki wskazującej na plik z danymi otwieranej mapy.
}
\newpage
\subsubsection{Pełnoekranowa wizualizacja}

Włączenie i wyłączenie pełnoekranowej wizualizacji jest możliwe poprzez wybór odpowiedniej opcji w menu
``Widok'' (patrz \ref{fig:view_on} oraz \ref{fig:view_off}).

\begin{figure}[H]
\centering
\subfloat[Włączanie]{\label{fig:view_on}\includegraphics{images/view_on.png}}
\hspace{1cm}
\subfloat[Wyłączanie]{\label{fig:view_off}\includegraphics{images/view_off.png}}
\caption{Pełnoekranowa wizualizacja}
\end{figure}


\subsubsection{Wizualizacja mapy}

% \parbox{1.0\textwidth}{
Edytowana mapa jest wizualizowana w prawej części okna aplikacji (patrz \ref{fig:visual}).

\begin{wrapfigure}{r}{6.5cm}
\centering
\includegraphics[width=6.5cm]{images/visual.png}
\caption{Oglądanie mapy}
\label{fig:visual}
\end{wrapfigure}

\noindent Legenda:
\begin{itemize}
 \item linia zielona - aktywny fragment siatki
 \item linia szara - nieaktywny fragment siatki
 \item linia żółta - linia siatki kontrolnej płatów Beziera
 \item czerwony punkt - aktywny punkt siatki kontrolnej płatów Beziera
\end{itemize}
\noindent Dostępne opcje:
\begin{itemize}
 \item obracanie mapy - przytrzymując lewy przycisk myszy możemy obracać mapę
 \item zbliżanie i oddalanie mapy - mapę możemy zbliżać i oddalać odpowiednio klawiszami ``+'' oraz `-`
 \item podnoszenie i opuszczanie mapy - mapę możemy opuszczać i podnosić odpowiednio klawiszami ``$\downarrow$'' oraz ``$\uparrow$''
\end{itemize}

% }

\subsubsection{Wybieranie obszaru edycji}

\parbox[t][4.5cm][t]{1.0\textwidth}{

\begin{wrapfigure}{r}{5cm}
\centering
\vspace{-20pt}
% \hspace{-20pt}
\includegraphics[width=5cm]{images/selection.png}
\caption{Wybór obszaru edycji}
\label{fig:selection}
\end{wrapfigure}

Wybór obszaru edycji jest możliwy poprzez zaznaczenie go na schematycznym podglądzie mapy (widok z góry)
w lewym górnym rogu aplikacji (patrz \ref{fig:selection}). Wybrany fragment mapy wyświetla się w części wizualizacyjnej.
}

\subsubsection{Tworzenie siatki punktów kontrolnych}

\parbox[t][3.5cm][t]{1.0\textwidth}{

\begin{wrapfigure}{r}{7cm}
\centering
\vspace{-10pt}
\includegraphics{images/new_control_points.png}
\caption{Tworzenie siatki punktów kontrolnych}
\label{fig:new_control_points}
\end{wrapfigure}

Stworzenie nowej siatki punktów kontrolnych jest możliwe poprzez formularz w lewej części okna aplikacji. Po wybraniu liczby
wierszy oraz kolumn siatka pojawia się na mapie w części wizualizacyjnej. Jej schematyczny podgląd jest widoczny w lewej dolnej
części okna aplikacji.
}

\subsubsection{Modyfikacja wysokości punktów siatki kontrolnej}

\parbox[t][7cm][t]{1.0\textwidth}{

\begin{wrapfigure}{r}{7cm}
\centering
\vspace{-10pt}
\includegraphics[width=7cm]{images/control_points.png}
\caption{Modyfikacja wysokości punktów siatki kontrolnej}
\label{fig:control_points}
\end{wrapfigure}

Modyfikacja wysokości punktów siatki kontrolnej jest możliwa poprzez ich wybór myszą na schematycznym podglądzie siatki
oraz ich podniesienie/opuszczenie suwakiem znajdującym się poniżej schematycznego podglądu siatki (patrz \ref{fig:control_points}).
Aktywacja punktów następuje poprzez ``kliknięcie`` punktu kontrolnego lub zaznaczenie całego obszaru; zaznaczenie kilku
punktów/obszarów po przytrzymaniu ''ctrl``.

Po zmianie wysokości punktów kontrolnych zmiany nanoszone są od razu na mapę,
co jest widoczne w części wizualizacyjnej.
}
% \newpage
\subsubsection{O programie}
\parbox[t][2cm][t]{1.0\textwidth}{


\begin{wrapfigure}{r}{5cm}
\centering
\vspace{-20pt}
\includegraphics[width=5cm]{images/about.png}
\caption{O programie}
\label{fig:about}
\end{wrapfigure}

Informacje o programie i autorach są dostępne poprzez wybór odpowiedniego elementu menu ''Pomoc`` (patrz \ref{fig:about})


}
% 
% \begin{figure}[H]
% \centering
% \includegraphics{images/about.png}
% \caption{O programie}
% \label{fig:about}
% 
% \end{wrapfigure}

% 
% \nopagebreak
% \begin{figure}[H]
% \centering
% \includegraphics{images/about.png}
% \caption{O programie}
% \label{fig:about}
% \end{figure}

% \subsection{Przykład}
%
% W poniższym rozdziale stworzymy przykładową mapę, zapiszemy ją, otworzymy i ponownie wyedytujemy.
%
% % \line(1,0){200cm}
% % \line(1,0){200cm}

\chapter{Wizualizacja 3D (mas-visualization)}
W tym rozdziale przedstawimy architekturę komponentu mas-visualization. Jest to fragment systemu odpowiedzialny za
wizualizację systemów wieloagentowych na poziomie rysowania scen. W aplikacji mas-editor został on wykorzystany
do modelowania powierzchni, zaś komponent mas-core używa go zarówno do rysowania siatki, jak agentów.

Mas-visualization wykorzystuje bibliotekę JOGL, która jest adapterem systemu OpenGL dla Javy.
Udostępnia ona dwa podstawowe obiekty \vb{javax.media.opengl.GL} oraz  \vb{javax.media.opengl.GLU}. Pierwszy z
nich odpowiada za kontakt z oryginalną biblioteką GL z implementacji w C (opcja kompilatora \vb{gcc} \vb{-lGL}),
drugi z biblioteką GLU (opcja \vb{-lGLU}). W bibliotece GL zostały zaimplementowane podstawowe funkcje systemu OpenGL,
takie jak rysowanie kształtów  w przestrzeni (punktów, krzywych, trójkątów, wielokątów etc.), ich kolorowanie,
przesuwanie, obracanie, skalowanie, teksturowanie oraz obsługa światła, cieniowanie czy odbicia. GLU jest natomiast
zestawem pomocniczych procedur mających ułatwiać pracę. Standardowo używa się procedur z biblioteki GLU do konfiguracji rzutni.

Nie jest naszą ambicją wyjaśnianie w tej pracy zagadnień technicznych związanych z działaniem OpenGL.
Zainteresowany czytelnik z łatwością znajdzie wiele doskonałych książek i poradników poświęconych tej tematyce.

Ten rozdział będzie skupiony na metodach integracji komponentu mas-visualization z innymi komponentami systemu
zaimplementowanymi w ramach pracy magisterskiej. Zamieszczony opis rysowania scen nie wymaga znajomości technologii
OpenGL.

\section{Fasady}
Wszystkie komponenty, które korzystają z biblioteki mas-visualization odwołują się do niej przez odpowiednią
\mas{fasadę}, które tworzą hierarchię klas (rys. \ref{fig:uml_fascade}). Wszystkie klasy będące
fasadami znajdują się w przestrzeni nazw \vb{pl.edu.mimuw.mas.visualization}. Głównym elementem w hierarchii jest
abstrakcyjna klasa \vb{AbstractVisualization}. Zawiera ona referencję do obiektu typu \vb{Chart} (zmienna
\vb{chart}), który reprezentuje wizualizowaną powierzchnię. \vb{AbstractVisualization} nigdy nie dokonuje zmian w
zmiennej \vb{chart}, ale możliwa jest zamiana wizualizowanej powierzchni na inną przy pomocy metody \vb{setChart}.

W przypadku mas-mapeditor zmienna \vb{chart} ustawiona jest na aktualnie tworzony obiekt. Wątek
renderujący i edytujący współdzielą pamięć w edytowanej instancji klasy \vb{Chart}, co pozwala oszczędzić pamięć i
zwiększyć wydajność animacji.

\vspace{0.5cm}

Architektura całego komponentu opiera się o pojęcie kontekstu renderowania. Jest to obiekt
przechowujący ustawienia kamery, kolorów oraz informacje o zaznaczonych elementach na planszy. Kontekst
jest współdzielony przez fasadę oraz klasę renderującą. Ten temat, jak i konstrukcja klas, zostanie szerzej omówiony w rozdziale
\ref{section:rysowanie_pow}.

\vb{AbstractVisualization} umożliwia posiadanie wielu widoków na planszę i manipulowanie nimi poprzez utrzymywanie
wielu kontekstów. Mamy do dyspozycji 4 metody do zarządzania kontekstami:

\begin{enumerate}
 \item \vb{createContext} - metoda tworzy kontekst wyświetlający fragment planszy opisany obiektem typu \vb{Area} i
 zwraca jego numer (deskryptor), w przypadku niepoprawnego opisu rzuca wyjątek \vb{WrongAreaException}.
 \item \vb{replaceContext} - metoda tworzy kontekst (patrz wyżej) i zastępuje aktualny kontekst nowym.
 \item \vb{toggleContext} - metoda ustawia aktualny kontekst o podanym numerze (deskryptorze), w przypadku nieznanego
 deskryptora rzuca wyjątek \newline \vb{ContextUnknownException}.
 \item \vb{toggleGlobalContext} - metoda ustawia aktualny kontekst na kontekst globalny. Kontekst globalny jest
 pierwszym (domyślnym) kontekstem i pokazuje całą planszę.
\end{enumerate}

\vb{AbstractVisualization} hermetyzuje ustawienia renderowania udostępniając innym komponentom jedynie deskryptory kontekstów.
Zarządzanie kontekstami jest realizowane przez wektor kontekstów \vb{localContext}. Utworzenie nowego
kontekstu polega na dodaniu elementu do wektora. Należy zauważyć, że nie jest możliwe usuwanie kontekstów, zamiast tego
możemy nadpisywać aktualny kontekst nowym. Ponadto zarządzanie kontekstami nie przewiduje wielowątkowości. W przypadku
użycia jednej instancji fasady przez wiele wątków mogą wystąpić niespodziewane błędy.

W ramach podstawowych funkcjonalności wizualizacyjnych realizowanych prze tę klasę możliwe
jest także zaznaczanie (wyróżnianie) elementów na planszy. Służą do tego metody:
\begin{enumerate}
 \item \vb{select} - metoda zaznacza wybrany obszar; jeśli nie jest on poprawny rzuca wyjątek
 \vb{WrongAreaException}.
 \item \vb{selectNone} - metoda wyłącza zaznaczenie, odznacza wszystko.
\end{enumerate}

\noindent Kolor zaznaczenia jest zapisywany w kontekście i obecnie nie można go zmieniać z poziomu fasady.

% \newpage

\begin{figure}[H]
\centering
% \hspace{-60pt}
\includegraphics[width=1.15\textwidth]{images/uml_fascade.png}
\caption{Hierarchia fasad mas-visualization}
\label{fig:uml_fascade}
\end{figure}
% \thispagestyle{empty}

% \clearpage


% \mbox{}
% \newpage


Kolejna warstwa w hierarchii to klasy \vb{ChartEditorBaseVisualization} i \newline
\vb{AgentBaseVisualization}. Rozszerzają one możliwości klasy nadrzędnej o funkcjonalności
potrzebne do wizualizacji w komponentach mas-mapeditor i mas-core. Aby rozróżnić rodzaje wizualizacji
klasa nadrzędna zawiera wirtualną metodę \vb{getType} zwracającą element typu \vb{contextType}.

\begin{verbatim}
public static enum contextType { EDITOR, VISUALIZATION };
\end{verbatim}

\noindent Metody \vb{getType} w klasach \vb{ChartEditorBaseVisualization}, \vb{AgentBaseVisualization}
zawracają odpowiednio wartości \vb{EDITOR}, \vb{VISUALIZATION}. Są one parametrem konstruktora
kontekstu wizualizacji. W zależności od niego rysowane są siatki kontrolne i inne elementy
służące do edycji bądź sama powierzchnia wraz z agentami.

\vspace{0.5cm}
Klasa \vb{ChartEditorBaseVisualization} wprowadza dwie nowe metody przeciążając parametry metod
\vb{createContext} i \vb{replaceContext} (zobacz rys \ref{fig:uml_fascade}). Pozwalają one na tworzenie
kontekstów (widoków) dla siatek kontrolnych (klasa \vb{ControlPoints}). Klasa \vb{AgentBaseVisualization}
wprowadza natomiast metody rejestrujące agentów do wyświetlania.

\begin{enumerate}
 \item \vb{registerAgentPossition} - dodaje agenta do wizualizacji
 \item \vb{deregisterAgentPossition} - usuwa agenta z wizualizacji
\end{enumerate}

Zarządzanie agentami jest realizowane przez pomocniczą klasę \vb{AgentPossitionManager}. Jest ona uruchamiana
jako osobny wątek i zaprojektowana z myślą o współbieżnych wywołaniach. Poniżej znajduje się kod źródłowy tej
klasy.

\begin{verbatim}
package pl.edu.mimuw.mas.visualization.agent;

public class AgentPossitionManager extends Thread {
  private HashSet<AgentPossition> agents = new HashSet<AgentPossition>();
  private AgentPossition[] clone;
  private boolean modified = true;

  public AgentPossition[] getAllAgentPossitions() {
    synchronized (this) {
      if (modified) {
        clone = agents.toArray(new AgentPossition[agents.size()]);
        modified = false;
      }
    }

    return clone;
  }

  public void registerAgentPossition(AgentPossition ap) {
    if (ap != null) {
      synchronized (this) {
        modified = agents.add(ap);
      }
    }
  }

  public void deregisterAgentPossition(AgentPossition ap) {
    if (ap != null) {
      synchronized (this) {
        modified = agents.remove(ap);
      }
    }
  }
}
\end{verbatim}

\noindent Klasa buforuje informacje o pozycjach agentów, których trzeba wizualizować na potrzeby silnika renderującego.
Jeśli agent zostanie dodany lub usunięty bufor jest odświeżany. Opis pozycji agenta - \vb{AgentPossition} -
jest współdzielony między komponentami mas-visualization i mas-core. Składa
się on z pól:

\begin{verbatim}
private String label;  // Wyświetlany napis nad agentem
private int x, y;      // Pozycja w przestrzeni
private float z;
private float[] color; // Kolor agneta tablica wartości [R, G, B]
                       // każdy kolor przyjmuje warotści od 0.0f do 1.0f
\end{verbatim}

Klasy \vb{ChartEditorBaseVisualization} oraz \vb{AgentBaseVisualization} realizują wszystkie funkcjonalności
potrzebne do wizualizacji. Nie zawierają jednak obsługi konkretnego płótna, zatem nie są jeszcze w stanie wyprodukować
obrazu.

Kolejna warstwa to konkretne fasady które są używane w systemie. Klasy \linebreak
\vb{ChartEditorWindowedVisualization} i \vb{AgentWindowedVisualization} używają wizualizacji w oknie AWT.
Tworzenie okna, inicjalizacja odpowiedniego płótna oraz spięcie całości jest realizowane poprzez klasę \vb{Window}.
Taki rodzaj wizualizacji sprawdza się bardzo dobrze w testach wizualizacji (zobacz rys. \ref{fig:test_node_size}), jest
także używany przy wizualizacji przez komponent mas-core.

\begin{figure}[H]
\centering
\includegraphics[width=8cm]{images/test_node_size.png}
\caption{Wizualizacja w oknie AWT przy użyciu klasy \vb{Window}}
\label{fig:test_node_size}
\end{figure}

Klasa \vb{ChartEditorVisualization} rysuje natomiast na dowolnym płótnie typu \vb{javax.media.opengl.GLCanvas},
będącym parametrem konstruktora. Fragment klasy \vb{ChartEditorVisualization} pokazany poniżej.

\begin{verbatim}
public ChartEditorVisualization(GLCanvas canvas, Chart chart) {
  super(chart);
  this.canvas = canvas;		
  this.canvas.addGLEventListener(renderer);
  this.animator = new Animator(this.canvas);
  animator.start();
}
\end{verbatim}

\section{Renderowanie}\label{section:rysowanie_pow}
W poprzednim podrozdziale pokazaliśmy jak wygląda dostęp do logiki renderującej z punktu widzenia komponentów zależnych
od mas-visualization. W tym podrozdziale opiszemy funkcjonowanie samej wizualizacji pojmowanej jako rysowanie scen
zgodnie z wymaganiami.

Wiemy, że kontekst renderowania jest kluczowym elementem komponentu mas-visualization. Klasa
\vb{ChartRendererContext} jest jego implementacją.
Jego idea polega na wyodrębnieniu parametrów używanych przez silnik renderujący do osobnej klasy.
Daje to możliwość łatwego \mas{przełączania kontekstów} - wystarczy
podmienić instancję kontekstu w klasie renderującej (\vb{ChartRenderer}).

\dir{Kontekst renderowania}
Jako podstawową własność renderowania kontekst opisuje wycinek przestrzeni jaki będzie wizualizowany na rzutni oraz kąt
obiektywu.
\begin{verbatim}
// parametry rzutowania
private final float frustumNear = 5.0f;
private final float frustumFar = 120.0f;
private final float frustumAngle = 30.0f;
\end{verbatim}
Na poniższym rysunku parametry \vb{frustumNear}, \vb{frustumFar} oraz \vb{frustumAngle} odpowiadają odpowiednio \vb{a},
\vb{b} oraz $\Theta$.

\begin{figure}[H]
\centering
\includegraphics[width=8cm]{images/frustum.png}
\caption{}
\label{fig:frustum}
\end{figure}

\noindent Ponadto kontekst określa początkowe położenie mapy oraz kąt pod jakim ma być obrócona (składowe X i Y
obrotu, Z = 0). Aktualnie mapa jest ustawiana w środku wyświetlanego obszaru równolegle do rzutni.
\begin{verbatim}
// domyślny widok na mapę
private final float[] defaultViewAngle = { 90.0f, 0.0f };
private final float[] defaultChartPosition = { 0.0f, 0.0f,	
                      -(frustrumFar - frustrumNear) / 2 - frustrumNear };
\end{verbatim}
Oprócz wartości domyślnych kontekst posługuje się wartościami tymczasowymi, równymi domyślnym w chwili początkowej.
Wartości te są zmieniane podczas interakcji z użytkownikiem (zobacz tabela \ref{tab:events}).
\begin{verbatim}
private float[] viewAngle;
private float[] chartPosition;
\end{verbatim}
Użytkownik może także zmieniać skalę z jaką mapa jest powiększana. Wartość parametru \vb{scaleOffsetRatio} mówi o ile
addytywnie zmienia się skala przy pojedynczym powiększeniu bądź pomniejszeniu (metody \vb{incScale} i
\vb{decScale}).
\begin{verbatim}
// powiększenie 	
private float scale;
private float scaleOffsetRatio = 0.035f;

private float viewZoom = 0.75f; 
\end{verbatim}


Kontekst definiuje także ile procentowo powinna maksymalnie zajmować wysokość i szerokość mapy na płótnie na początku
wizualizacji. Procedura \vb{autoscale} oblicza odpowiednią wartość zmiennej \vb{scale} na podstawie
\vb{viewZoom}, wielkości mapy, odległości mapy od rzutni i kąta $\Theta$ (rys. \ref{fig:frustum}). Dzięki takiemu
rozwiązaniu niezależnie od rozmiaru mapy zawsze widoczny jest cały obszar.

\begin{figure}[H]
\centering
\includegraphics[width=15.5cm]{images/scale.png}
\caption{}
\label{fig:scale}
\end{figure}

\begin{verbatim}
// wielkość obiektów
private float nodeRatio = 0.3f;
private float nodeThreshold = 0.8f;
\end{verbatim}

\newpage

\begin{figure}[H]
% \centering
\vspace{-70pt}
\hspace{-40px}
\includegraphics[height=1.13\textheight]{images/uml_renderer.png}
\caption{\vb{ChartRenderer} i \vb{ChartRendererContext}}
\label{fig:uml_renderer}
\end{figure}
\thispagestyle{empty}

\clearpage

% \mbox{}
% \newpage

Podobne rozwiązanie zastosowano w celu dopasowywania wielkości punktów kontrolnych siatek Bezier. Metoda \vb{getNodeScale}
(poniżej) wylicza skalę, z jaką należy rysować punkty kontrolne.
\begin{verbatim}
public float getNodeScale() {
  float result = 1.0f;
		
  if (scale < 1f) {
    result -= (1 - scale) * nodeThreshold;
  }
		
  return result * nodeRatio / scale;
}
\end{verbatim}

Jeśli skala jest większa od \vb{1} to rysowane punkty kontrolne mają stały rozmiar. Zauważmy, że dzielenie przez
\vb{scale} równoważy skalowanie (czyli de facto mnożenie razy \vb{scale}) całej mapy. Jeśli \vb{scale} jest
mniejsze lub równe \vb{1}, wówczas obserwujemy liniowe zmniejszenie punktów kontrolnych w zależności od
\vb{scale}. Gdy \vb{scale} dąży do \vb{0} wartość \vb{getNodeScale} dąży do \vb{nodeThreshold *
nodeRatio / scale};

\vspace{0.5cm}

\noindent Kontekst określa fragment mapy jaki ma być wyświetlany. Dozwolone fragmenty są prostokątami opisywanymi
przez cztery liczby naturalne, będące współrzędnymi skrajnie lewego dolnego oraz skrajnie prawego górnego
punktu. Opis przechowywany jest w tablicy \vb{viewArea}. Wyświetlane fragmenty są powiększane o margines równy
\vb{viewMargin} kratek (gdy to możliwe). Margines jest rysowany bez skośnych elementów siatki aby wyróżniał się od
wizualizowanego fragmentu (zobacz rys. \ref{fig:margin}).

Warto zwrócić uwagę, że kontekst jest w pewnym sensie obiektem jednokrotnego użytku. Niemożna zmienić mapy ani
wyświetlanego fragmentu po utworzeniu instancji.
\begin{verbatim}
// renderowany fragment siatki 
public final Chart chart;
public final int[] viewArea;

private int viewMargin = 5;
\end{verbatim}

\begin{figure}[t]
\centering
\includegraphics[width=15.5cm]{images/margin.png}
\caption{}
\label{fig:margin}
\end{figure}

\begin{verbatim}	
// początkowe ekstrema
private float min;
private float max;
\end{verbatim}
Wartości min i max są to maksymalne i minimalne wysokości na mapie. Parametry te są wykorzystywane przy obliczaniu
przesunięcia mapy wzdłuż osi Y (rys. \ref{fig:frustum}), tak by użytkownik odniósł wrażenie, że mapa jest umieszczona
centralnie na płótnie.

\vspace{0.5cm}

\noindent Kolejnym elementem przechowywanym w kontekście są zaznaczenia. Dla uproszczenia implementacji w 
aktualnej wersji można zaznaczyć (wyróżnić kolorem) jeden prostokątny obszar na mapie; zaznaczenie innego spowoduje automatyczne
odznaczenie poprzedniego.
\begin{verbatim}
// zaznaczanie
private int[] selection = new int[4];
private boolean showSelected = true;
\end{verbatim}
Zmienna \vb{showSelected} jest indykatorem zaznaczania. Do obsługi zaznaczeń kontekst udostępnia trzy metody:
\begin{enumerate}
 \item \vb{void select(int x0, int y0, int x1, int y1)} metoda zaznacza przecięcie prostokąta $((x_0, y_0),(x_1,
 y_1))$ z wyświetlanym obszarem (zmienna \vb{viewArea}) oraz ustawia flagę \vb{showSelected} na \vb{true}.
 \item \vb{void select(Area area)} metoda analogiczna do poprzedniej, ale prostokąt jest przekazywany przez obiekt typy \vb{Area}.
 \item \vb{void selectNone()} metoda wyłączająca zaznaczenie, ustawia flagę \vb{showSelected} na \vb{false}.
\end{enumerate}

\vspace{0.5cm}

\noindent Kolejnym elementem określanym przez kontekst jest ustawienie rozproszonego światła, domyślnie kolor ustawiany jest
na szary średniej mocy.
\begin{verbatim}
// parametry oświetlenia
private float[] lightPosition = { 0.0f, 0.0f, 0.0f, 0.0f };
private float[] lightAmbient = { 0.6f, 0.6f, 0.6f };
\end{verbatim}
\vspace{0.5cm}

\noindent Kontekst definiuje również kolory podstawowych elementów. Są one definiowane w systemie RGB podając
intensywność składników (wartości od \vb{0.0f} do \vb{1.0f}); czwarty parametr jest opcjonalny (opisuje
współczynnik $\gamma$). Domyślnie używane są wartości pochodzące z palety kolorów Tango (\vb{http://tango.freedesktop.org}).

\begin{itemize}
 \item \vb{bgColor} - kolor tła
 \item \vb{activeGridColor} - kolor zaznaczenia
 \item \vb{inactiveGridColor} - kolor siatki
 \item \vb{activeControlPointColor} - kolor zaznaczenia punktów kontrolnych płata Bezier
 \item \vb{inactiveControlPointColor} - kolor siatki kontrolnej płata Bezier
\end{itemize}
Jedyną bezpośrednią metodą zmiany powyższych
wartości jest edycja kodu źródłowego i wpisanie nowych wartości.

\dir{Renderowanie powierzchni}
Skoro wiemy już co kontroluje i jak działa kontekst wizualizacji możemy dokonać przeglądu kodu logiki renderującej.
Najpierw jednak przedstawimy listę zdarzeń, którymi użytkownik może wpływać na proces renderowania scen.

Klasa \vb{ChartRenderer} implementuje \vb{IRenderer}. Jest to pusty interfejs służący agregacji:
\begin{itemize}
 \item \vb{GLEventListener} - zdarzenia związane z renderowaniem
 \item \vb{MouseListener} - zdarzenia związane z kliknięciami myszy
 \item \vb{MouseMotionListener} - zdarzenia związane z ruchem myszy
 \item \vb{KeyListener} - zdarzenia związane z klawiaturą
\end{itemize} 

\vspace{0.3cm}

Trzy ostatnie z powyższych interfejsów umożliwiają użytkownikowi kontakt z aplikacją zmieniając parametry
aktualnego kontekstu. Klasa \vb{ChartRenderer} obsługuje następujące zdarzenia, przy pomocy których użytkownik może
modyfikować kontekst renderowania.
\begin{table}[H]
 \label{tab:events} 
 \begin{center}
  \begin{tabular}{|l|l|}
   \hline naciśnięcie $\uparrow$ & przesunięcie mapy do góry\\
   \hline naciśnięcie $\downarrow$ & przesunięcie mapy do dołu\\
   \hline naciśnięcie $\rightarrow$ & przesunięcie mapy w prawo\\
   \hline naciśnięcie $\leftarrow$ & przesunięcie mapy w lewo\\
   \hline naciśnięcie \vb{+}(\vb{=}) & powiększenie obrazu\\
   \hline naciśnięcie \vb{-} & pomniejszenie obrazu\\
   \hline naciśnięcie \vb{Esc} & przywrócenie początkowego obrazu\\
   \hline przytrzymanie i przesunięcie kursora & obrót mapy względem jej środka\\
   \hline
  \end{tabular}
 \end{center}
 \caption{Interakcja z użytkownikiem}
\end{table}

\newpage

Samo renderowanie jest obsługiwane przez zaimplementowanie metod interfejsu \vb{GLEventListener}:
\begin{enumerate}
 \item \vb{init} - metoda wywoływana dokładnie raz przy inicjalizacji renderowania. Odpowiedzialna za ustawienie
 światła, koloru tła, rejestrację nasłuchiwania zdarzeń myszy i klawiatury oraz wygenerowanie często używanych elementów.
 W celu optymalizacji sześcian (reprezentacja agenta) jest generowany raz (metoda \vb{drawCube}) i przechowywany w
 pamięci podręcznej na karcie graficznej. Deskryptor odpowiedniej \mas{listy} jest zapamiętywany z zmiennej
 \vb{glCube}. Do wygenerowanej listy odwołuje się poleceniem \vb{gl.glCallList(glCube)}, gdzie \vb{gl} to instancja
 klasy \vb{GL}.
 \item \vb{display} - metoda wywoływana w nieskończonej pętli przez wątek animujący. Odpowiedzialna za rysowanie scen,
 w zależności od typu kontekstu przewidziane są różne scenariusze zachowania.
\begin{verbatim}
drawGrid(gl);
switch (context.getType()) {
  case EDITOR:
    drawControlPoints(gl);
    break;
  case VISUALIZATION:
    drawAgents(gl);
    break;
}
\end{verbatim} 
 \item \vb{reshape} - metoda wywoływana po zmniejszeniu obszaru wizualizacji, także na początku animacji. Odpowiedzialna
 za ustawienie rzutowania, po zmianie rozmiaru płótna należy dopasować rozmiar rzutni.
\end{enumerate}
Do rysowania konkretnych obiektów służą prywatne metody:
\begin{enumerate}
 \item \vb{drawGrid} - metoda rysuje siatkę (\vb{Chart}) ograniczoną do pod obszaru (parametr \vb{viewArea} kontekstu)
 wraz z marginesami. Ponadto wyróżnia kolorem zaznaczone fragmenty siatki.
 \item \vb{drawControlPoints} - metoda rysuje siatkę kontrolną płata Bezier wyróżniając zaznaczone punkty kontrolne
 kolorem.
 \item \vb{drawAgents} - metoda rysuje agentów na podstawie danych z klasy pomocniczej \vb{AgentPossitionManager}.
\end{enumerate}

\chapter{Wizualizacja systemu wieloagentowego (mas-core)}
Komponent mas-core, jak powiedzieliśmy na wstępie, jest kluczowym elementem całej pracy. Jest w nim zrealizowana
warstwa integracji wizualizacji (komponent mas-visualization) z zewnętrzną platformą wieloagentową JADE. Logicznie
komponent mas-core można podzielić na trzy powiązane ze sobą części:
\begin{enumerate}
 \item rozszerzenia JADE ułatwiające konstrukcję agentów
 \item agenci realizujący usługi
 \item graficzne interfejsy użytkownika ułatwiające współpracę z agentami.
\end{enumerate}
Będziemy je omawiać w kolejnych podrozdziałach. Na koniec rozdziału pokażemy jak korzystać ze stworzonych
rozwiązań z poziomu graficznego interfejsu.

\section{Rozszerzenia JADE} \label{section:JADE}
Ponownie, jak w przypadku OpenGL, nie jest naszym celem opisywanie architektury platformy JADE. Zainteresowany
czytelnik znajdzie doskonały opis systemu JADE
w \cite{JDB}. W celu zrozumienia działania systemu opisywanego w tej pracy przedstawimy jedynie kluczowe elementy
działania platformy wieloagentowej JADE.

\begin{citeenv}
``JADE (Java Agent DEvelopment Framework) is a software Framework fully implemented in Java language. It simplifies the
implementation of multi-agent systems through a middle-ware that complies with the FIPA specifications and through a
set of graphical tools that supports the debugging and deployment phases\ldots''
\textnormal{źródło \vb{http://jade.tilab.com/}}
\end{citeenv}
JADE jest biblioteką implementującą specyfikację wieloagentową FIPA w języku Java. Udostępnia aplikacjom
infrastrukturę wieloagentową, jednak nie implementuje żadnego paradygmatu wieloagentowego jak np. BDI. Komponent
mas-core używa JADE do zarządzania agentami i komunikacją.

\vspace{0.5cm}
Podstawową klasą JADE jest \vb{jade.core.Agent}. Każdy agent jest jej podklasą. Komunikacja z platformą odbywa
się poprzez przeciążenie metod klasy \vb{Agent}, z których warto wymienić:
\begin{itemize}
 \item \vb{void setup()} - metoda wywoływana podczas inicjalizacji agenta
 \item \vb{void takeDown()} - metoda wywoływana podczas usuwania agenta.
\end{itemize}
Akcje, które wykonuje agent, zwane dalej \mas{zachowaniami}, są podklasami klasy \linebreak
\vb{jade.core.behaviours.Behaviour}. Do zarządzania nimi służą metody:
\begin{itemize}
 \item \vb{addBehaviour(Behaviour b)} - metoda dodająca nowe zachowanie
 \item \vb{removeBehaviour(Behaviour b)} - metoda usuwająca zachowanie.
\end{itemize}
Nowe zachowanie agenta tworzy się dziedzicząc z klasy \vb{Behaviour} (lub jej podklasy) i  nadpisując metody:
\begin{itemize}
 \item \vb{void action()} - metoda implementująca zachowanie
 \item \vb{boolean done()} - metoda wykonywana po zakończeniu metody \vb{action} w informująca, czy zachowanie
 zakończyło się, czy dalej jest aktywne.
\end{itemize}
Warto nadmienić, że domyślnie w JADE każdy agent jest realizowany w jednym wątku. Powoduje to wzrost wydajności (obsługa
wątków w Javie jest dość powolna) oraz eliminuje problemy synchronizacji. Brak wielowątkowości nie oznacza, że agent
nie może wykonywać wielu zachowań (\vb{Behaviour}) jednocześnie. Autorzy JADE zaimplementowali prosty
system kolejkowania. Zachowania gotowe do wykonania tworzą kolejkę FIFO, z której agent pobiera zachowanie, wykonuje metodę
\vb{action}, następnie \vb{done}. Jeśli zachowanie nie skończyło się wstawia je ponownie na koniec kolejki. System nie obsługuje
wywłaszczania wobec czego zachowania powinny być możliwie proste i nie blokować wykonania innych (poza szczególnymi przypadkami).
JADE udostępnia wiele gotowych szkieletów typowych zachowań, między innymi:
\begin{itemize}
 \item \vb{CyclicBehaviour} - zachowanie zawsze aktywne, cyklicznie wykonujące jakieś akcje
 \item \vb{OneShotBehaviour} - zachowanie wykonywane jednokrotnie
 \item \vb{SequentialBehaviour} - zachowanie wykonujące inne zachowania sekwencyjnie
 \item \vb{TickerBehaviour} - zachowanie wykonujące się periodycznie (co określoną jednostkę czasu)
 \item \vb{WakerBehaviour} - zachowanie wykonujące się z opóźnieniem.
\end{itemize}

\vspace{0.5cm}

Komponent mas-core definiuje trzy dodatkowe zachowania, znajdujące się w pakiecie
\vb{pl.edu.mimuw.mas.agent.behaviour}.

% \newpage

\begin{figure}[H]
\centering
\begin{sideways}
\includegraphics[width=1.0\textwidth, angle=-90]{images/uml_behaviour_rotate.png}
\end{sideways}
\caption{Zachowania}
\label{fig:uml_behaviour}
\end{figure}

\thispagestyle{empty}
\clearpage


% \mbox{}
% \newpage

\script{DFRegisterBehaviour} Zachowanie dziedziczące z \vb{OneShotBehaviour} które ma na celu uproszczenie
rejestrowania usług przez agentów. JADE udostępnia \mas{dziennik} w którym agenci mogą rejestrować się jako dostawcy
usług, tak by inni agenci mogli ich odnaleźć. Z usługami można połączyć ontologie, które rozumie agent dostawca.
\begin{verbatim}
DFRegisterBehaviour(Agent agent, String serviceType,
  String serviceOntology)
\end{verbatim}
W konstruktorze podaje się agenta, nazwę usługi (\vb{serviceType}) oraz nazwę ontologii (\vb{serviceOntology}).

\script{MutableTimedBehaviour} Zachowanie będące klonem \vb{TickerBehaviour} pozwalające na manipulowanie czasem
pomiędzy kolejnymi wywołaniami. Komponent mas-core wprowadza singleton \linebreak \vb{pl.edu.mimuw.mas.tools.PeriodModifier}
określający mnożnik czasu dla zachowań agentów. \vb{MutableTimedBehaviour} w konstruktorze przyjmuje parametr
określający względny kwant czasu w milisekundach. Rzeczywiste opóźnienie jest wyliczane przy każdej iteracji używając
wartości zwracanej przez metodę \vb{getPeriod()}.

\begin{verbatim}
public MutableTimedBehaviour(Agent a, long period) {
  super(a);
  this.period = period;
  this.modifier = PeriodModifier.getInstance();
}

private long getPeriod() {
  currentScale = modifier.getScale();
  return ((Double) (period * currentScale)).longValue();
}
\end{verbatim}
Takie rozwiązanie pozwala na manipulowanie prędkością rozgrywki przez użytkownika oraz ułatwia obserwację systemów
wieloagentowych.

\script{ServerBehaviour} Abstrakcyjne zachowanie ułatwiające agentom nasłuchiwanie wiadomości. Metoda 
\begin{verbatim}
public void setMessageTemplate(MessageTemplate mt) {
  this.mt = mt;
} 
\end{verbatim}
pozwala na filtrowanie wiadomości. Odpowiedź jest wypełniana w abstrakcyjnej metodzie \vb{boolean doAction(ACLMessage
msg, ACLMessage reply)}. Jeśli metoda zwraca wartość \vb{true} wówczas odpowiedź jest odsyłana.

\vspace{0.5cm}

Oprócz zachowań, mas-core wprowadza ontologię \vb{viz-core-ontology}. Jest to wspólna ontologia dla agenta
wizualizującego w środowisku 2D, 3D oraz dla agenta logującego zdarzenia. Dla agentów wizualizujących ontologia
wprowadza predykat \vb{Possition} opisujący pozycję agenta, poniżej przykład w języku KQML.
\begin{verbatim}
(Possition 
  Dyzio@localhost:1099/JADE 
  (Point :x 110 :y 129 :z 1.0) 
  (Color :r 233 :g 241 :b 17)
  20090625T202159464Z
)
\end{verbatim}
Pozycja jest określona przez podanie nazwy agenta, punktu w przestrzeni, koloru w jakim agent chce być narysowany i
czasu w jakiej znajdował się w tej pozycji.

Dla agenta logującego zdarzenia ontologia wprowadza pojęcie \vb{LogEntry},
przykładowy komunikat w języku KQML poniżej.
\begin{verbatim}
(LogEntry 
  :agentId Dyzio@localhost:1099/JADE 
  :value "log message" 
  :date 20090625T203516029Z
)
\end{verbatim}
Wysłanie komunikatu logującego wymaga podania nazwy agenta (\vb{agentId}), treści komunikatu (\vb{value}) i daty
wysłania (\vb{date}). 

Wszystkie powyższe pojęcia są zaimplementowane jako klasy Javy i znajdują się w pakiecie
\vb{pl.edu.mimuw.mas.ontology}; klasa \vb{VisualizationCoreOntology} jest odpowiedzialna za konfigurację ontologii
\vb{viz-core-ontology}.

\section{Agent wizualizujący} \label{section:vizAgent}
Komponent mas-core definiuje dwa rodzaje agentów wizualizujących: agent wizualizujący 3D i agent wizualizujący 2D.
\begin{itemize}
 \item \vb{pl.edu.mimuw.mas.agent.Visualization2DAgent} - wizualizacja 3D
 \item \vb{pl.edu.mimuw.mas.agent.Visualization3DAgent} - wizualizacja 2D
\end{itemize}
Wizualizacja 2D wykorzystuje takie same metody jak wizualizacja 3D, ale mapa, na której odbywa się wizualizacja jest
płaska, a pozycje agentów są na nią rzutowane.


Agenci implementują interfejs \vb{IAgentMonitorBE}. Służy on do kontaktu widoku (użytkownika) z agentem.
Użycie interfejsu ma chronić autonomiczność agenta, ponadto umożliwia używanie jednego widoku przez wiele typów
agentów. Interfejs definiuje metody:
\begin{itemize}
 \item \vb{void toggleDisplayStrategy()} - metoda mówiąca agentowi, by zmienił strategię wizualizowania agentów.
 Agent wizualizujący ma dwie strategie: dla nowych agentów może albo ich wyświetlać na płótnie od razu albo nie. Gdy nowi
 agenci nie są automatycznie wyświetlani użytkownik musi ręcznie \mas{zarejestrować} agenta w celu jego wizualizacji na
 płótnie
 \item \vb{boolean getDisplayStrategy()} - metoda informująca jaka jest strategia, czy nowi agenci są domyślnie
 wizualizowani na płótnie
 \item \vb{void deregisterAgentPossition(AgentPossitionExtended ap)} - metoda usuwająca agenta z wizualizacji
 \item \vb{void registerAgentPossition(AgentPossitionExtended ap)} - metoda dodająca (rejestrująca) agenta do
 wizualizacji.
\end{itemize}

Architektura agenta wizualizacyjnego jest dość naturalna. Agent 3D przyjmuje trzy parametry:
\begin{enumerate}
 \item \vb{Chart} opisujący mapę
 \item \vb{ITabContener} opisujący okno, w którym będą wyświetlane informacje o wizualizacji oraz
konfiguracja (więcej o \vb{ITabContener} w podrozdziale \ref{section:agentGUI})
 \item trzeci typu logicznego determinujący, czy domyślnie wizualizować agentów
\end{enumerate}
Po starcie, w pierwszej kolejności agent rejestruje usługę wizualizacyjną przy
pomocy zachowania \vb{DFRegisterBehaviour}.
\begin{verbatim}
addBehaviour(new DFRegisterBehaviour(this, SERVICE_TYPE, 
               VisualizationCoreOntology.ONTOLOGY_NAME));
\end{verbatim}
Zmienna statyczna \vb{SERVICE\_TYPE} opisuje nazwę usługi. Usługi są skojarzone z ontologią \vb{viz-core-ontology}
(agenci mas-core nie posługują się innymi ontologiami). Ponadto komunikacja z nimi odbywa się w języku KQML, jak w
przykładach w poprzednim podrozdziale. Dzięki takiej metodzie komunikacji możliwe jest wizualizowanie systemów napisanych w dowolnej technologii
wieloagentowej zgodnej ze specyfikacją FIPA. Następnie agent zaczyna obsługiwać klientów przy pomocy zachowania
\vb{ServerBehaviour}, agent tworzy ad-hoc instancję podklasy z przedefiniowaną metodą \vb{doAction} odpowiedzialną za
mapowanie komunikatów KQML na obiekty Javy oraz za tworzenie odpowiedzi na komunikaty. Jeśli agent zgodzi się na
wizualizację odsyła wiadomość typu \mas{agree}, w przeciwnym przypadku typu \mas{refuse}.



% \vspace{0.5cm}
% \newpage
Agenci klienci wizualizacji są opisywani poprzez instancje klasy \linebreak \vb{AgentPossitionExtended} rozszerzającej klasę
\vb{AgentPossition} z komponentu mas-visualization o dodatkowe pola:
\begin{itemize}
 \item \vb{String aid} - nazwa (identyfikator) agenta
 \item \vb{boolean printable} - czy agent jest wizualizowany
 \item \vb{Date lastEventDate} - data ostatniego komunikatu
 \item \vb{int eventCount} - licznik komunikatów
 \item \vb{int r, g, b} - kolory w notacji RGB o 8-bitowej głębi
 \item \vb{boolean overrideColor} - czy agent może ustalać swój kolor.
\end{itemize}
Instancje są dzielone między wątkiem agenta, panelem administracyjnym\linebreak(\vb{AgentMonitorPanel}) i komponentem
mas-visualization. Agent wizualizujący utrzymuje tablice mieszającą z informacjami o agentach
\begin{verbatim}
private final HashMap<String, AgentPossitionExtended> agents
\end{verbatim}
Analogiczna tablica znajduje się w \vb{AgentMonitorPanel}.
% \vspace{0.5cm}



% \newpage
% 
% 
% 
% \begin{sidewaysfigure}
% \centering
% 
% \begin{figure}[H]
% % \hspace{-60pt}
% \includegraphics[height=1.0\textheight,angle=-90]{images/uml_viz_agents.png}
% \caption{Agenci wizualizujący}
% \label{fig:uml_viz_agents}
% \end{figure}
% \end{sidewaysfigure}
% 
% 
% 
% \thispagestyle{empty}
% 
% \clearpage
% 
% \mbox{}
% \newpage

Zarządzanie wizualizacją agentów jest zrealizowane w metodzie \vb{processRequest}.
\begin{verbatim}
private boolean processRequest(
  String aid, int x, int y, float z, 
  int r, int g, int b, Date lastEventDate) 
\end{verbatim}
Jest ona wywoływana w metodzie \vb{doAction}, a jej wynikiem jest informacja o zgodzie lub odmowie wizualizacji. Jeśli
agent poda swoją pozycję poza mapą lub niepoprawny kolor zostanie automatycznie usunięty z wizualizacji. Jeśli dla
agenta istnieje już wpis w tablicy mieszającej to jest aktualizowany. Kolor agenta na ekranie jest aktualizowany tylko
w sytuacji, gdy zmienna \vb{overrideColor} jest ustawiona na \vb{true}. Jeśli agent nie posiada wpisu w tablicy
\vb{agents} wpis jest tworzony, odpowiednie dane są wysyłane do widoku i zależnie od strategii jest wizualizowany na
ekranie.


\section{Agent logujący} \label{section:logAgent}
Architektura w przypadku agenta logującego jest analogiczna jak w przypadku agentów wizualizujących.
% Warto zwrócić uwagę na podobieństwo poniższego diagramu do diagramu \ref{fig:uml_viz_agents}.
Agent implementuje interfejs
\vb{ILogBE}. Ma on zapewniać izolację agenta od części czysto obiektowej. \vb{ILogBE} definiuje metody:
\begin{itemize}
 \item \vb{void toggleActivity()} - metoda przełączająca stan aktywności agenta. Agent logujący może znajdować się w
 jednym z dwóch stanów: aktywnym, wówczas loguje zdarzenia oraz nieaktywnym wówczas ignoruje komunikaty od
 klientów.
 \item \vb{boolean isActive()} - metoda pozwalająca stwierdzić, czy agent jest w stanie aktywnym.
\end{itemize}


Podobnie jak poprzednio agent w pierwszej kolejności rejestruje się w \mas{dzienniku} korzystając z zachowania
\vb{DFRegisterBehaviour}. Następnie tworzy instancję podklasy \vb{ServerBehaviour} z przedefiniowaną metodą
\vb{doAction}. Agent nigdy nie odsyła powiadomienia - metoda \vb{doAction} zawsze zwraca wartość \vb{false}.
Ciało metody jest znacznie prostsze niż poprzednio. Jako że agent pełni rolę proxy między agentami a graficznym
interfejsem, jego rola polega jedynie na publikowaniu otrzymanych wiadomości w postaci graficznej (więcej w \ref{section:agentGUI}).

\newpage

\thispagestyle{empty}

\begin{figure}[H]
\centering
\begin{sideways}
\includegraphics[width=1.0\textheight]{images/uml_log_agents.png}
\end{sideways}
\caption{Agent logujący}
\label{fig:uml_log_agents}
\end{figure}

\newpage


\section{Agent klient} \label{section:clientAgent}
W celu ułatwienia tworzenia systemów korzystających z komponentu mas-core stworzyliśmy abstrakcyjnego agenta
\vb{ClientAgent} rozszerzającego klasę \vb{Agent}. Celem agenta jest ułatwienie dostępu do usług wizualizacyjnych i
logowania. Agent inicjalizuje potrzebne ontologie, udostępnia metodę \vb{boolean setServiceAgents()} znajdującą
agenta wizualizującego 3D, 2D oraz agenta logującego zdarzenia w \mas{dzienniku}. Metoda zwraca wartość \vb{true} w gdy
wszyscy agenci zostaną odnalezieni, \vb{false} w przeciwnym przypadku. Klasa udostępnia publiczne metody
\begin{itemize}
 \item \vb{getViz3DAgent()} -metoda zwracająca identyfikator agenta wizualizującego 3D
 \item \vb{getViz2DAgent()} - metoda zwracająca identyfikator agenta wizualizującego 2D; 
 \item \vb{getLogAgent()} - metoda zwracająca identyfikator agenta logującego.
\end{itemize}
Agent korzystający z usług wizualizacyjnych powinien dziedziczyć po klasie \vb{ClientAgent} oraz w metodzie \vb{setup()}
wywoływać \vb{setServiceAgents()}. 

\section{Graficzne powłoki agentów} \label{section:agentGUI}
Przedstawimy teraz możliwości i metody interakcji użytkownika z agentami dostarczającymi usługi. Wcześniej w
\ref{subsection:oanel} omówimy jeszcze techniczny detal pominięty wcześniej.

\subsection{Panel administracyjny}\label{subsection:oanel}
Część graficzna naszego systemu składa się z trzech elementów: okna wizualizacji 3D, okna wizualizacji 2D oraz panelu
administracyjnego. W poprzednim rozdziale omówione zostały metody jakimi odbywa się wizualizacja systemów wieloagentowych
i edytora powierzchni w oknach wizualizacji. Teraz powiemy parę słów o panelu administracyjnym.

Panel administracyjny ma na celu zebranie formatek konfiguracyjnych wszystkich agentów w jednym miejscu. Jest
zaimplementowany w klasie \vb{pl.edu.mimuw.mas.gui. MainWindow}. Poniżej pusty panel administracyjny. 

Pusty panel umożliwia jedynie kontrolowanie prędkości systemu wieloagentowego przez zmienianie parametrów singletonu
\vb{PeriodModifier}. Poruszając suwakiem w lewym dolnym rogu w prawo zwiększamy prędkość, w lewo zmniejszamy. 

Klasa \vb{MainWindow} implementuje interface \vb{ITabContener}, wprowadza on metody mające zarządzać zakładkami
\begin{itemize}
 \item \vb{void addTab(Agent myagent, String name, JPanel panel)} - metoda dla agentów do dodania zakładek
 \item \vb{void addTab(String name, JPanel panel)} - metoda do dodawania zakładek przez inne byty.
\end{itemize}



\begin{figure}[H]
\centering
\includegraphics[width=11cm]{images/empty_panel.png}
\caption{Pusty panel administracyjny}
\label{fig:empty_panel}
\end{figure}

Agenci definiują swoje formatki w pakiecie \vb{pl.edu.mimuw.mas.agent.gui}, formatki agentów dziedziczą z klasy
\vb{JPanel} (Swing). Formatki umożliwiają kontakt użytkownika z agentami podczas działania systemu, opisowi
konkretnych zastosowań jest poświęcona sekcja \ref{subsection:funkcjonalnosci}. Agenci podczas startu dostają obiekt
realizujący \vb{ITabbContainer}. Jeśli chcą udostępniać swój panel konfiguracyjny dodają go poprzez wykonanie metody
\vb{addTab}.

% \vspace{0.5cm}


\begin{figure}[H]
\centering
% \vspace{-20pt}
\includegraphics[width=11cm]{images/admin_tabs.png}
\label{fig:admin_tabs}
\end{figure}
\vb{MainWindow} wyświetla panele agentów w postaci zakładek posortowanych alfabetycznie według nazw podawanych przez
agentów podczas dodawania (parametr \vb{name}).


\newpage

\begin{figure}[H]
\centering
\begin{sideways}
\includegraphics{images/uml_tabs.png}
\end{sideways}
\caption{Kontener zakładek}
\label{fig:uml_tabs}
\end{figure}

\thispagestyle{empty}

\clearpage



\subsection{Funkcjonalności} \label{subsection:funkcjonalnosci}

\subsubsection{Logowanie}

Każdy z agentów istniejących w systemie może, przy użyciu funkcji \vb{void log()}, logować informacje, które programista
uznał za ważne lub ułatwiające analizę problemu. Osobna zakładka w panelu administracyjnym umożliwia ich przeglądanie, filtrowanie
oraz zapis do zewnętrznego pliku tekstowego (patrz rys. \ref{fig:admin_log}).

\begin{figure}[H]
\centering
% \vspace{-20pt}
\includegraphics{images/admin_log.png}
\caption{Logowanie}
\label{fig:admin_log}
\end{figure}

Aby zapisać wyświetlone logi w zewnętrznym pliku tekstowym, należy wcisnąć przycisk ``zapisz logi'', po czym wybrać plik docelowy.

\begin{figure}[H]
\centering
% \vspace{-20pt}
\includegraphics[width=10cm]{images/admin_save.png}
\caption{Wybór pliku docelowego}
\label{fig:admin_save}
\end{figure}


\subsubsection{Filtrowanie wyświetlanych agentów}

Wyszukiwanie agentów o podanej nazwie (lub jej części) jest możliwe poprzez opcje filtrowania. Po wpisaniu frazy w 
komórce filtru, w aktywnej zakładce pozostaną wiersze jedynie tych agentów, których nazwa zawiera podany ciąg znaków.

\begin{figure}[H]
\centering
% \vspace{-20pt}
\includegraphics{images/admin_filter.png}
\caption{Filtrowanie}
\end{figure}

\subsubsection{Zmiana koloru agenta}

Kolor, używany do wyświetlania agenta w oknach wizualizacyjnych, można zmienić klikając na kolorowe pole w wierszu edytowanego
agenta.

\begin{figure}[H]
\centering
\subfloat{\includegraphics[height=130pt]{images/admin_color_change}}
\hspace{10pt}
\subfloat{\includegraphics[height=130pt]{images/admin_color_pick}}
\caption{Zmiana koloru agenta}
\end{figure}

\subsubsection{Sortowanie agentów}

Poprzez kliknięcie w nagłówek kolumny w tabeli z agentami, możemy posortować wiersze zgodnie z wartościami w danej kolumnie.
Kolejne kliknięcie odwraca kolejność sortowania.

\subsubsection{Wyłączenie wyświetlania agenta}

Wyłączenie wyświetlania agenta jest możliwe poprzez odznaczenie pola w danym wierszu (patrz rys. \ref{fig:admin_agent_off}).
W efekcie agent nie jest rysowany na planszy, jednak jego akcje są nadal wykonywane i może on kooperować z pozostałymi agentami.

\begin{figure}[H]
\centering
\includegraphics{images/admin_agent_off.png}
\caption{Wyłączenie wyświetlania agenta}
\label{fig:admin_agent_off}
\end{figure}

\subsubsection{Zmiana nazwy agenta}

Nazwę agenta można zmienić klikając na komórkę w tabeli w kolumnie ``Nazwa''. Pole to staje się edytowalne i umożliwia
wprowadzenie nowej nazwy.

\begin{figure}[H]
\centering
\includegraphics{images/admin_agent_name.png}
\caption{Zmiana nazwy agenta}
\label{fig:admin_agent_nam}
\end{figure}


\chapter{Podsumowanie}
Podstawowym celem pracy było stworzenie rozwiązania dającego możliwość łatwego wizualizowania systemów 
wieloagentowych w środowisku 3D. Napisaliśmy dwie aplikacje mające zrealizować ten cel. 

Pierwszą z nich jest edytor powierzchni trójwymiarowych oparty o płaty Bezier'a. Bazuje on na autorskich 
implementacjach algorytmów modelujących i w swojej budowie jest minimalistyczny. Udostępnione zostały jedynie podstawowe funkcjonalności,
które okazały się jednak w zupełności wystarczające.

W ramach rozwoju aplikacji interesujące byłoby stworzenie formatu pliku, który pozwalałby na zapamiętanie parametrów siatek
kontrolnych modelowanych obszarów. Kolejną możliwością usprawnienia byłaby zmiana modelu matematycznego na oparty o krzywe NURBS,
co mogłoby się przyczynić do poprawienia jakości edytora.

Drugą aplikacją, która powstała jest agent obsługujący silnik rysujący sceny trójwymiarowe (OpenGL). Dzięki ich prostocie
są one czytelne, a cała aplikacja działa płynnie. Niestety na modelowanych powierzchniach brak naturalnych przeszkód takich jak rzeki, drzewa czy 
zabudowania. Uzupełnienie ich bardzo poprawiłoby realizm symulacji.

Ze względu na użyciu standardu - platformy JADE, jako bazy dla naszego rozwiązania wiele istniejących systemów
można już teraz szybko zwizualizować. Ponadto, poprzez sprawne zastosowanie nowoczesnych technologii,
proces instalacji jest prosty i nie wymaga wiedzy na temat struktury danych źródłowych.

%
% CZESC II
%

\part{System wieloagentowy}\label{part:mas}

\chapter{Wstęp}
Tematyką tej części pracy, jak i rozważanego przykładu, jest kolektywne rozwiązywanie problemów. Jest ona rozwijana w Instytucie Informatyki
Wydziału Matematyki i Informatyki Uniwersytetu Warszawskiego przy współpracy z Uniwersytetem w Groningen. Prace prowadzone
były na gruncie logik wielomodalnych i doprowadziły do zdefiniowania logiki \mas{team-log} (zob. \cite{BDK1}, \cite{BDK2}). 
Autorzy przedstawiają alternatywne podejście do problemu modelowania współpracy niekorzystające z tych teorii.

%mam kiepskie notatki co tu mialo byc. To co mam zapisane:
%\begin{itemize}
% \item dziedzina problemu
% \item tematyka rozwijana na UW i uniwersytecie w Groeningen (odnosniki do prac keplicz)
% \item wspolne postawy: kolektywna intencja, kolektywne zobowiazanie
% \item jest to rozwiaznie problemu rozwazanego na zajeciach (dlatego razem pisalismy)
% \item wykorzystane logiki wielomodalne
%\end{itemize}
%masz cos dodatkowego z czego daloby sie skleic rozsadny wstep?

\chapter{Problem poszukiwania łosia}
Rozważmy następujący problem: Z ogrodu zoologicznego w Zurychu uciekł łoś. W jego poszukiwaniu wysłano $k$-elementową
grupę robotów naziemnych oraz $l$ bezzałogowych jednostek latających (UAV). Roboty mają zlokalizować i schwytać uciekiniera
zanim wyrządzi sobie lub innym krzywdę.

Jednostki latające wyposażone są w \mas{detektor}. Działa on w promieniu $r_p$ i pozwala określić
pozycję łosia. W wyniku niedokładnych odczytów urządzenie, z prawdopodobieństem $p_p$, myli się
i wskazuje uciekiniera tam, gdzie go nie ma.

Roboty wyposażone są w \mas{miotacze pocisków usypiających} oraz \mas{odstraszacze}. Pociski z miotacza
można wystrzelić na odległość $d_m$, a prawdopodobieństwo trafienia w cel wynosi $p_m$. Odstraszacz działa na odległość
$d_o$. Po jego użyciu łoś ucieka w kierunku przeciwnym do kierunku źródła straszenia. Ponadto roboty naziemne poruszają się
znacząco wolniej od poszukiwanego agenta.

Łosia należy uśpić i bezpiecznie przetransportować do zoo. Ze względu na dużą moc pocisków usypiąjących roboty nie mogą
trafić uciekiniera więcej niż jednym pociskiem ze względu na duże ryzyko śmierci.
\newline

Problem ten był dla nas motywacją do napisania tej pracy i stworzenia systemu wizualizacji przedstawianego w części
pierwszej. W tym rozdziale podamy jego bardziej formalne sformułowanie i osadzimy w łatwiejszym do implementacji
kontekście.

\section{Środowisko}
Ze względów praktycznych będziemy rozważać powyższy problem w dyskretnej przestrzeni z dyskretnym czasem. Proces polowania na
łosia nazwiemy umownie \mas{rozgrywką}, a teren na którym się ona toczy \mas{planszą}.
\newline
\newline
Plansza jest siatką rozmiarów $n \times m$ z przyporządkowaną każdemu punktowi wysokością (w
implementacji są one obiektami typu \vb{Chart}). \mas{Odległość} na planszy jest zdefiniowana poprzez
indukowaną metrykę Euklidesową $\mathbb{R}^2$. Formalnie odległość punktu $a = (x_a, y_a, \cdot)$ od punktu $b = (x_b,
y_b, \cdot)$ należących do planszy określa się wzorem $$d(a, b) = \sqrt{(x_a - x_b)^2 + (y_a - y_b)^2}.$$ 
\newline
\newline
Ponadto na plansze nałożone są dodatkowe warunki:

\begin{itemize}
 \item Na planszy nie istnieją przeszkody poza ukształtowaniem terenu
 \item Mogą istnieć miejsca, do których nie może dojść agent
 \item Nie istnieją miejsca, których nie może zobaczyć agent powietrzny;
\end{itemize}

\section{Agenci}
W rozgrywce uczestniczy agent \mas{łoś}, który odgrywa rolę uciekiniera oraz pozostali agenci, których można podzielić na
dwie grupy.
\begin{enumerate}
 \item Agenci naziemni - roboty poruszające się po powierzchni planszy, których celem jest złapanie łosia. Wyróżniamy dwa
typy agentów: \mas{łowca} oraz \mas{sznaucer}. Zadaniem sznaucerów jest straszenie łosia tak, by umożliwić łowcom
trafienie go miotaczem pocisków usypiających.
 \item Agenci powietrzni - W tej grupie wyróżniamy jeden typ - \mas{helikopter}. Jednostki te poruszają się nad planszą i
 obserwują teren z góry w poszukiwaniu łosia. Po jego zlokalizowaniu helikopter rozsyła do agentów naziemnych
 informację o jego pozycji.
\end{enumerate}

\subsection{Agent typu \mas{łoś}}\label{def:los}
Łoś co $t_{ln}$ wybiera w sposób losowy nowy \mas{cel} na planszy. Po jego wyznaczeniu
porusza się w nowo obranym kierunku najkrótszą drogą.
\newline
\newline
Agent ten charakteryzuje się poniższymi cechami:
\begin{itemize}
 \item porusza się z prędkością nie większą niż $v_l$
 \item jest podatny na działanie odstraszacza
 \item jeśli jest poddany działaniu odstraszacza to ucieka z prędkością $v_l$, w kierunku wyznaczonym przez
 wypadkową siłę odstraszania (w przypadku zerowej siły wypadkowej kierunek jest losowy)
 \item jeśli nie jest poddany działaniu odstraszacza porusza się w stronę \mas{celu}, tak że każdy krok wykonuje
 z losową prędkością nie większą niż $v_l$
\end{itemize}

\subsection{Agent typu \mas{łowca}}\label{def:lowca}
Zadaniem agenta typu łowca jest wystrzelenie pocisku usypiającego, celem unieruchomienia łosia.
\newline
\newline
Agent ten charakteryzuje się poniższymi cechami:
\begin{itemize}
 \item porusza się z prędkością $v_n$, takiej że $v_n < v_l$ (patrz def. \mas{Łoś})
 \item jest wyposażony w miotacz pocisków usypiających
 \item jest wyposażony w detektor łosia
 \item potrafi komunikować się z pozostałymi agentami
\end{itemize}

\subsection{Agent typu \mas{sznaucer}}\label{def:sznaucer}
Zadaniem agenta typu sznaucer jest wystraszenie łosia w taki sposób, aby ułatwić łowcom oddanie celnego strzału.
\newline
\newline
Agent ten charakteryzuje się poniższymi cechami:
\begin{itemize}
 \item porusza się z prędkością $v_n$, takiej że $v_n < v_l$ (patrz def. \mas{Łoś})
 \item jest wyposażony w odstraszacz
 \item jest wyposażony w detektor łosia
 \item potrafi komunikować się z pozostałymi agentami
\end{itemize}

\subsection{Agent typu \mas{helikopter}}\label{def:helikopter}
Zadaniem agentów powietrznych jest namierzenie łosia i przekazanie informacji o jego pozycji
agentom naziemnym. Po odnalezieniu helikoptery śledzą uciekiniera, tak by w każdej chwili wiedzieć gdzie jest.
\newline
\newline
Agent ten charakteryzuje się poniższymi cechami:
\begin{itemize}
 \item porusza się najszybciej ze wszystkich agentów, z prędkością $v_p$
 \item porusza się na stałej wysokości
 \item nie może wylecieć poza planszę
 \item nie rozbija się
 \item może działać do zakończenia rozgrywki (ma nieskończoną ilość paliwa)
 \item potrafi komunikować się z pozostałymi agentami
\end{itemize}

Niech helikopter będzie w ustalonym punkcie $a$. Wówczas jego \mas{obszar widoczności} to zbiór
punktów na planszy odległych od $a$ o mniej niż $r_p$ (\mas{promień widoczności}).
\newline
\newline
Dodatkowo wiemy, że:

\begin{itemize}
 \item czas przeszukiwania obszaru widoczności wynosi $t_p$
 \item jeśli łoś jest w obszarze widoczności to zostanie zauważony
 \item jeśli łosia nie ma w obszarze widoczności to z prawdopodobieństwem $p_p$ zostanie błędnie zauważony w losowym
 punkcie tego fragmentu planszy
 \item jeśli agent jest proszony o zweryfikowanie, czy w danym punkcie łoś jest widoczny to podaje odpowiedź bezbłędnie.
\end{itemize}

\chapter{Wieloagentowe rozwiązanie problemu znajdowania łosia}
W tym rozdziale przedstawimy w jaki sposób działają poprzednio zdefiniowani agenci. Naszym celem jest stworzenie systemu
wieloagentowego, który zorganizuje poszukiwanie łosia na planszy. Dokładniej, opracowanie komunikacji i koordynacji
działań agentów tak by było możliwe wykonanie ``klasycznej nagonki'' przy jednoczesnym zagwarantowaniu bezpieczeństwa
łosia.

Działanie systemu uznajemy za zakończone sukcesem, jeśli łoś zostanie odnaleziony i trafiony nie więcej niż dwoma
pociskami. Za zakończone porażką, jeśli łoś zostanie trafiony więcej niż dwoma pociskami.

\section{Agenci naziemni}

Zadaniem agentów naziemnych, zwanych w dalszej części rozdziału robotami, jest umożliwienie jednemu
z nich wystrzelenia pocisku w kierunku łosia. W tym celu, przy użyciu odstraszacza,
agenci typu sznaucer straszą uciekiniera w taki sposób, że porusza się on w stronę jednego z
łowców, co ma pozwolić na oddanie strzału. Proces ten nazwijmy \mas{nagonką}.

Aby zorganizować działanie poszczególnych jednostek, roboty są dzielone na grupy, tak że w każdej w nich są albo łowcy
albo sznaucerzy. Spośród nich wybierane są te, które w danej chwili mogą najskuteczniej przeprowadzić
nagonkę.
\newline\newline
Algorytm postępowanie robotów można podzielić na następujące kroki:

\begin{enumerate}
 \item Otrzymanie informacji o pozycji łosia
 \item Organizacja agentów w grupy
 \item Wybranie takich dwóch grup różnego typu (jednej łowców i jednej sznaucerów), dla których proces nagonki będzie
 najefektywniejszy, tzn. łoś znajdzie się najbliżej łowców. Wybieramy taką parę, dla której wartość poniższego
 wyrażenia jest największa: $$min(\angle ABC, 2\pi - \angle ABC), \textrm{ gdzie}$$
 \begin{itemize}
  \item[A] środek grupy sznaucerów, wyznaczony przez średnią pozycję jej członków,
  \item[B] pozycja łosia,
  \item[C] środek grupy łowców, wyznaczony przez średnią pozycję jej członków.
 \end{itemize}
 Wybrane grupy będziemy nazywać grupami \mas{aktywnymi}
 \item Nagonka - straszenie łosia w kierunku łowców. Uwaga! Faza ta jest przerywana wraz
 z otrzymaniem nowej pozycji uciekiniera
\end{enumerate}

Przeanalizujmy nietrywialne fazy algorytmu - organizację w grupy, wybór grup aktywnych oraz nagonkę.

\subsection{Organizacja w grupy}

Na wstępie zdefiniujmy:

\begin{definitionenv}
Grupa to zbiór agentów, z których jeden jest wyróżniony i nazywany \mas{liderem}
\end{definitionenv}

Algorytm podziału na grupy opiera się na cesze robotów zwanej charyzmą, opisanej przy pomocy pojedynczej
dodatniej liczby rzeczywistej. Określa ona maksymalny potencjał agenta do bycia liderem, a zatem szanse
przyłączenia się innych do jego grupy. W praktyce wpływ na otoczenie maleje wraz z odległością.

\begin{definitionenv}
Efektywna charyzma to funkcja uzależniająca charyzmę od odległości od danego agenta. Opisuje z jaką
efektywnością oddziałuje na nas agent $X$ o charyzmie $a$, będący w odległości $d$. Jest zatem funkcją:
$$echar: \mathbb{R}^+\times \mathbb{R}^+\rightarrow \mathbb{R}^+$$
gdzie pierwszym argumentem jest charyzma, drugim odległość. Funkcja $echar$ musi spełniać następujące warunki:
\begin{enumerate}
 \item Dla danej charyzmy $echar$ jest funkcja malejącą
 \item $echar(a,0) = a$
\end{enumerate}
\end{definitionenv}

Liderem staje się ten agent, dla którego jego własna charyzma jest wyższa od efektywnej charyzmy
wszystkich pozostałych agentów. Robot nie będący liderem podłącza się do grupy tego agenta, który ma względem
niego najwyższą efektywną charyzmę.

Aby uprościć powstałą strukturę chcielibyśmy, aby nie miała ona więcej niż jednego poziomu, tzn. aby nie było
takich 3 różnych agentów A, B oraz C, że A należy do grupy B, zaś B należy do grupy C. Funkcja $echar$ musi
zatem spełniać dodatkowo warunek:
$$echar(a_1, d_1) = echar(a_2, d_2) \Rightarrow echar(a_1, d_1 + d_3) = echar(a_2, d_2 + d_3)$$

Jedną z wielu możliwych funkcji na efektywną charyzmę spełniającą wszystkie postawione kryteria jest
$\frac{1}{d+\frac{1}{a}}$, gdzie $a$ jest charyzmą, a $d$ odległością. Jej fragment zaprezentowano na
rysunku \ref{fig:echar_graph}.
\newpage
\begin{figure}[ht]
\centering
\includegraphics[width=7cm]{images/echar_graph.png}
\caption{Wykres funkcji $\frac{1}{d+\frac{1}{a}}$ dla $d\in [0..5]$ i $a\in [0..1]$}
\label{fig:echar_graph}
\end{figure}

\noindent Ostatecznie algorytm podziału na grupy wygląda następująco:
\begin{verbatim}
broadcast(self, self.charisma)
charisma_info = collect_charisma_info()
best_agent = self
best_echar = echar(self.charisma, 0)
for agent, charisma in charisma_info:
   curr_echar = echar(charisma, d(self, agent)))
   if curr_echar > best_echar:
      best_agent = agent
      best_echar = curr_echar
if best_agent is not self:
   self.is_leader = False
   join(best_agent)
else:
   self.is_leader = True
\end{verbatim}

\subsection{Wybór aktywnych grup}

W tej fazie musimy wybrać takie dwie grupy różnego typu (jedną łowców i jedną sznaucerów), że efektywność
nagonki będzie maksymalna, tzn. że łoś będzie najbliżej łowców.

\begin{definitionenv}
Dokładność straszenia określa jak blisko grupy łowców grupa sznaucerów może przegonić
Łosia. Jest ona zdefiniowana jako wartość wyrażenia:
$$\frac{min(\angle ABC, 2\pi - \angle ABC)}{\pi}, \textrm{ gdzie}$$
\begin{itemize}
 \item[A] środek grupy sznaucerów, wyznaczony przez średnią pozycję jej członków,
 \item[B] pozycja łosia,
 \item[C] środek grupy łowców, wyznaczony przez średnią pozycję jej członków.
\end{itemize}
\end{definitionenv}

\noindent Algorytm możemy podzielić na dwie osobne fazy:

\subsubsection*{Faza I - stworzenie par kandydujących}

Liderzy grup łowców ogłaszają przetargi na grupę sznaucerów o najwyższym współczynniku straszenia.
Po otrzymaniu ofert wybierana jest najlepsza. Dodatkowo liderzy kierują się poniższymi regułami:

\begin{enumerate}
 \item akceptowane są tylko zgłoszenia ze współczynnikiem straszenia większym od 0,5
 \item w przypadku otrzymania dwóch identycznych ofert wybierana jest dowolna z nich
 \item w przypadku nie otrzymania ofert spełniających warunki grupa wycofuje się z dalszych części algorytmu
\end{enumerate}

\noindent Liderzy grup sznaucerów, po otrzymaniu informacji o wszystkich otwartych przetargach, zgłaszają swoją ofertę
tej grupie łowców (jej liderowi), dla której ich współczynnik straszenia jest najwyższy.

\subsubsection*{Faza II - wybór najlepszej pary}

Liderzy grup łowców ogłaszają dokładność straszenia swojej pary oraz odległość od grupy sznaucerów.
Wybierana jest ta para, dla której dokładność straszenie jest najwyższa. W przypadku dwóch lub więcej takich samych
wyników, decyduje odległość - im mniejsza tym lepiej. Jeśli obydwa kryteria zawiodą (są co najmniej dwie pary o identycznej
dokładności i odległości) algorytm kończy się niepowodzeniem i musimy rozpocząć całą organizację od nowa (tzn. czekamy
na informację o pozycji łosia).

\subsection{Straszenie łosia}

% \begin{wrapfigure}{r}{7cm}
\begin{figure}[ht]
\centering
\includegraphics{images/flee_dist.png}
\caption{Obliczanie dystansu ucieczki}
\label{fig:flee_dist}
% \end{wrapfigure}
\end{figure}


Celem tej fazy jest przestraszenie łosia w taki sposób, aby uciekł w miejsce, które jest
najbliżej grupy łowców. Ze względu na fakt, że prędkość ucieczki przed odstraszaczem
jest znana i stała, to obliczenie potrzebnego czasu straszenia staje się trywialne:

\begin{enumerate}
 \item Oblicz dystans ucieczki $D_{flee}$ zgodnie ze wzorem: $$D_{flee}=\frac{D_{dh}^2-D_{hl}^2-D_{dl}}{2D_{dl}}$$
 \item Oblicz czas ucieczki $t_{flee}$ zgodnie ze wzorem: $$t_{flee}=\frac{D_{flee}}{v_l}$$
\end{enumerate}

\subsection{Strzelanie}

Proces strzelania odbywa się w sposób niezależny od pozostałych akcji. Gdy łoś jest w zasięgu strzału,
agent rozgłasza chęć wystrzelenia pocisku. Jeśli w przeciągu $x$ jednostek czasu nikt nie zgłosi analogicznej prośby
uznaje się, że prośba została zaakceptowana i agent może strzelać. W przypadku, gdy agent otrzyma zgłoszenie
o strzale po tym jak sam je wystosował, czeka losową liczbę jednostek czasu (nie większą niż $y$) i wystosowuje ponowne zgłoszenie. Agent nie
może zgłosić chęci oddania strzału jeśli w ciągu ostatnich $t_m$ jednostek czasu (patrz def. łosia, rozdział \ref{def:los})
otrzymał takie zgłoszenie od innego agenta lub jeśli łoś został wcześniej trafiony pociskiem.

\subsection{Ruch}

Agenci poruszają się w taki sposób, aby być jak najbliżej łosia, przy zachowaniu maksymalnej odległości pomiędzy sobą.
Wybór ruchu następuje zgodnie z poniższym algorytmem:

\begin{enumerate}
\item Wybierz jednostkowy wektor ruchu $v$, równoległy do jednej ze współrzędnych, taki że po jego wykonaniu odległość agenta od łosia byłaby
najmniejsza
\item Weź dwa wektory jednostkowe $v_1$ i $v_2$, takie że $v\bot v_1$, $v\bot v_2$ oraz $v_1 \neq v_2$
\item Spośród wektorów ruchu $v$, $v+v_1$, $v+v_2$ wybierz ten, dla którego po jego wykonaniu odległość agenta od pozostałych agentów byłaby
największa
\end{enumerate}

Prędkość poruszania się agenta zależy od jego odległości od łosia - im jest ona mniejsza, tym agent porusza się szybciej.
W przypadku braku informacji o pozycji łosia, agent porusza się losowo z minimalną prędkością.

\section{Agenci powietrzni}
Na początku rozgrywki agenci powietrzni są umieszczeni losowo (z równomiernym rozkładem prawdopodobieństwa) nad
planszą. Agenci nie wiedzą gdzie jest łoś i muszą go odnaleźć, aby przekazać agentom naziemnym informacje o jego
położeniu.

Działanie helikopterów składa się z trzech fundamentalnych elementów opisanych w podrozdziałach poniżej.
Na początku agenci muszą podzielić się pracą (konkretny algorytm jest tematem rozdziału
\ref{subsection:przydzial_obszarow}). Następnie każdy z nich szuka uciekiniera w przydzielonym mu obszarze, co zostało opisane w 
\ref{subsection:patrolowanie}. Ostatecznie po jego odnalezieniu, aby nie wprowadzać agentów naziemnych w
błąd, inny agent powietrzny weryfikuje czy na pewno znaleziono łosia. Algorytm weryfikacji został opisany w
\ref{subsection:weryfikacja}.

\subsection{Przydział obszarów poszukiwań}\label{subsection:przydzial_obszarow}
Spośród wszystkich agentów powietrznych przed rozpoczęciem rozgrywki wybierany jest jeden, który pełni rolę lidera.
Na początku działania każdy helikopter wysyła do niego swoją pozycję. On zaś dokonuje podziału planszy
na \mas{obszary poszukiwań} i przydziela je agentom. Do tego czasu pozostają oni bezczynni.
\newline

Niech ilość helikopterów na planszy będzie równa $l$ oraz niech $k = \lceil \log_2 l \rceil$. Rozpatrzmy poniższą definicję:

\begin{definitionenv}
Obszarem poszukiwań stopnia $n$ nazywamy obszar, który powstaje poprzez przepołowienie, wzdłuż krótszego z boków, obszaru
stopnia $n - 1$, dla $n \geq 1$. Obszar poszukiwań stopnia $0$ jest całą planszą. W przypadku krawędzi równej długości
wybór nie ma znaczenia.
\end{definitionenv}

Lider dokonuje podziału planszy na obszary poszukiwań stopnia $k$. Nie trudno sprawdzić, że różnych obszarów poszukiwań
stopnia $k$ jest $2^k \geq l$. Dla większej jasności zauważmy, że w przypadku gdy jest $5$ agentów należy podzielić
planszę na $8$ fragmentów. Na poniższym rysunku przedstawiono przykładowy podział planszy, kolorowymi kulkami oznaczono
agentów na ich początkowych pozycjach.

\begin{figure}[H]
\centering
\includegraphics[width=7cm]{images/search_area.png}
\caption{Podział planszy dla pięciu agentów}
\label{fig:search_area}
\end{figure}

\begin{definitionenv}
Niech $O_1$, $O_2$ obszary poszukiwań stopnia $k$. Powiemy, że $O_1$ jest bezpośrednio na lewo od $O_2$ gdy spełnione są
następujące warunki:
\begin{eqnarray*}
\min \lbrace c : (c, \cdot) \in O_1\rbrace & < & \min \lbrace c : (c, \cdot) \in O_2 \rbrace\\
\min \lbrace r : (\cdot, r) \in O_1\rbrace & = & \min \lbrace r : (\cdot, r) \in O_2 \rbrace.
\end{eqnarray*}
Analogicznie powiemy, że $O_1$ jest bezpośrednio ponad $O_2$ gdy:
\begin{eqnarray*}
\min \lbrace c : (c, \cdot) \in O_1\rbrace & = & \min \lbrace c : (c, \cdot) \in O_2 \rbrace\\
\min \lbrace r : (\cdot, r) \in O_1\rbrace & > & \min \lbrace r : (\cdot, r) \in O_2 \rbrace.
\end{eqnarray*}
\end{definitionenv}

Korzystając z tych pojęć w zbiorze obszarów poszukiwań dowolnego, ustalonego stopnia możemy wprowadzić relację
porządku. Każdemu obszarowi $O$ możemy bowiem przyporządkować parę $(c, r)$, gdzie $c$ to liczba obszarów poszukiwań
bezpośrednio na lewo od $O$, a $r$ to liczba obszarów poszukiwań bezpośrednio ponad $O$. Porządek ten
definiujemy jako porządek leksykograficzny na takich parach i oznaczamy przez $\rho$.

Ponadto obszary poszukiwań tego samego stopnia o równej pierwszej współrzędnej nazywamy kolumną a o równej drugiej
współrzędnej wierszem. Wszystkie te pojęcia przydadzą się nam w dalszej części rozdziału.
\newline

Znając pozycję każdego z agentów lider musi określić przyporządkowanie agentów do obszarów poszukiwań. Proces ten
odbywa się w dwóch fazach.

\subsection*{Faza I - początkowe przyporządkowanie}
W tej fazie każdemu agentowi przyporządkowuje się dokładnie jeden obszar poszukiwań stopnia $k$.
Niech \vb{A} będzie zbiorem helikopterów bez przypisanego obszaru poszukiwań oraz niech \vb{L} będzie listą
obszaru poszukiwań stopnia $k$ uporządkowaną względem porządku $\rho$. Wówczas procedura przypisywania agentom obszarów
poszukiwań jest następująca:
\begin{verbatim}
while A not empty:
   l = L.next()
   a = nearest(l, A)
   assign(l, a)
   remove(A, a)
\end{verbatim}

W powyższym pseudokodzie kolejnym elementom listy przypisuje się najbliższy wolny helikopter. Funkcja
\vb{nearest} liczy odległość każdego agenta ze zbioru \vb{A} od środka obszaru poszukiwań \vb{l}, w wyniku
działania zwraca agenta o minimalnej odległości. Metoda \vb{assign} dokonuje przydzielenia obszaru \vb{l}.
\newline

Poniżej (rys. \ref{fig:search_area_assigned1}) przykład wykonania tej procedury w systemie z rysunku
\ref{fig:search_area}. Obszary poszukiwań agentów zostały wyróżnione ich kolorami. Na szaro zaznaczono
obszary nie przyporządkowane.

\begin{figure}[H]
\centering
\includegraphics[width=7cm]{images/search_area_assigned1.png}
\caption{Ilustracja do fazy I dla pięciu agentów}
\label{fig:search_area_assigned1}
\end{figure}

\subsection*{Faza II - rozciąganie}
Jeśli $2^k > l$ to w fazie I zostaną pominięte niektóre obszary poszukiwań. Celem fazy II jest przypisanie każdego obszaru 
poszukiwań do dokładnie jednego agenta.

\begin{factenv}
W każdym wierszu obszary przypisane do agentów są bezpośrednio na lewo od tych nieprzypisanych do agentów.
\end{factenv}

\begin{factenv}
Niech $\delta_i$ będzie ilością nieprzypisanych obszarów poszukiwań w $i$-tym wierszu. Wówczas zachodzi następująca
nierówność: $\forall_i\; \delta_i \leq \frac{m}{2}$, gdzie m to liczba kolumn.
\end{factenv}

Korzystając z powyższych faktów możemy rozdzielić obszary poszukiwań wśród agentów tak, by każdy agent miał co najwyżej
dwa z nich do patrolowania.

Dla $i$-tego wiersza ostatnich $\delta_i$ agentów będzie kontrolować dwa obszary poszukiwań, nie jeden jak do tej pory.
Jeśli $\delta_i > 0$ to w $i$-tym wierszu pierwszy agent od prawej będzie kontrolował obszar w ostatnich dwóch kolumnach,
kolejny agent w kolumnie trzeciej i czwartej od końca itd. Tę procedurę nazwiemy \mas{rozciąganiem}.
\newline

Ponieważ dla każdego wiersza $\delta_i < \frac{m}{2}$, to nigdy nie zabraknie agentów do rozciągnięcia, co
gwarantuje, że każdy obszar zostanie przydzielony jakiemuś agentowi. Ponadto w tej metodzie agenci są stosunkowo równo
obdzieleni obowiązkami - żaden agent nie kontroluje obszaru ponad dwa razy większego niż dowolny inny agent.
\newline

Poniżej (rys. \ref{fig:search_area_assigned2}) ostateczne przyporządkowanie obszarów poszukiwań do agentów w
przykładowym systemie z rysunku \ref{fig:search_area}. Rozciąganiu poddani zostali agenci o kolorach
morskim, fioletowym i czerwonym.

\begin{figure}[H]
\centering
\includegraphics[width=7cm]{images/search_area_assigned2.png}
\caption{Ostateczny podział planszy między agentów}
\label{fig:search_area_assigned2}
\end{figure}

\subsection{Szukanie łosia}\label{subsection:patrolowanie}
Po przypisaniu obszaru poszukiwań agent zaczyna jego \mas{patrolowanie}. Polega ono na systematycznym
poruszaniu się po wyznaczonym terenie i jednoczesnym kontrolowaniu planszy w promieniu widoczności agenta.
Trasa, po której porusza się agent przebiega wzdłuż czerwonej łamanej w kierunku zgodnym ze strzałkami (rysunek \ref{fig:snake_move}).

\begin{figure}[H]
\centering
\includegraphics[width=7cm]{images/snake_move.png}
\caption{``ruch węża''}
\label{fig:snake_move}
\end{figure}


Patrolowanie zaczyna się w punkcie $1$, który jest odległy o $r_p$ (promień widoczności) zarówno od górnej jak i od lewej
krawędzi. Agent zatrzymuje się we wszystkich ``narożnikach'' łamanej, a między nimi co $2 r_p$. Wówczas sprawdza
czy w jego promieniu widoczności nie ma łosia. 

% \vspace{0.5cm}
% \newpage

% \noindent W implementacji procedura wygląda następująco:
\newpage
\begin{verbatim}
public enum MoveTrend { UP, DOWN, LEFT, RIGHT; }

public static MoveTrend getNextSearchPosition
(Area area, Position cur, Position dest, MoveTrend trend) {
  if(!area.isInArea(cur.x, cur.y)) {      
    getInitialSearchPosition(area, dest);
    return MoveTrend.RIGHT;
  }
  int[] realArea = area.getArea();
  if(trend == MoveTrend.RIGHT) {
    dest.x = Math.min(cur.x + 2 * Range.HELICOPTER_SEARCH_RANGE, 
         realArea[Area.X1] - Range.HELICOPTER_SEARCH_RANGE);
    if(dest.x == realArea[Area.X1] - Range.HELICOPTER_SEARCH_RANGE) {
      trend = MoveTrend.DOWN;
    }      
  } else if(trend == MoveTrend.DOWN) {
    dest.y = Math.max(cur.y - 2 * Range.HELICOPTER_SEARCH_RANGE, 
             realArea[Area.Y0] + Range.HELICOPTER_SEARCH_RANGE);
    if(dest.x == realArea[Area.X1] - Range.HELICOPTER_SEARCH_RANGE) {
      trend = MoveTrend.LEFT;  
    } else {
      trend = MoveTrend.RIGHT;
    }
  } else if(trend == MoveTrend.LEFT) {
    if(dest.y == realArea[Area.Y0] + Range.HELICOPTER_SEARCH_RANGE) {
      dest.x = Math.max(cur.x - 2 * Range.HELICOPTER_SEARCH_RANGE, 
               realArea[Area.X0] + Range.HELICOPTER_SEARCH_RANGE);
      if(dest.x == realArea[Area.X0] + Range.HELICOPTER_SEARCH_RANGE) {
        trend = MoveTrend.UP;  
      }        
    } else {
      dest.x = Math.max(cur.x - 2 * Range.HELICOPTER_SEARCH_RANGE, 
               realArea[Area.X0] + 3 * Range.HELICOPTER_SEARCH_RANGE);
      if(dest.x == realArea[Area.X0] +
                          3 * Range.HELICOPTER_SEARCH_RANGE) {
        trend = MoveTrend.DOWN;
      }
    }      
  } else if(trend == MoveTrend.UP) {
    dest.y = Math.min(cur.y + 2 * Range.HELICOPTER_SEARCH_RANGE, 
             realArea[Area.Y1] - Range.HELICOPTER_SEARCH_RANGE);
    if(dest.y == realArea[Area.Y1] - Range.HELICOPTER_SEARCH_RANGE) {
      trend = MoveTrend.RIGHT;  
    }
  }
  return trend;
}

public static void getInitialSearchPosition(Area area, Position dest) {
  int[] realArea = area.getArea();
  dest.x = realArea[Area.X0] + Range.HELICOPTER_SEARCH_RANGE; 
  dest.y = realArea[Area.Y1] - Range.HELICOPTER_SEARCH_RANGE;
}
\end{verbatim}
\vspace{0.5cm}

Jest to fragment klasy \vb{pl.edu.mimuw.mas.util.PositionHelper}. Metoda \newline\vb{getNextSearchPosition}
przyjmuje jako parametry (w kolejności występowania) obszar poszukiwań, aktualną pozycję agenta, nową pozycję agenta (do
wyznaczenia) i aktualny kierunek. Jako wynik zwraca nowy kierunek poszukiwań, w którym powinien udać się agent.
\newline

Gdy agent rozpozna w danym punkcie nad planszą łosia zaczyna \mas{śledzenie}. Należy podkreślić, iż jeśli nie 
pomylił się, to śledzenie polega na lataniu nad łosiem. W przeciwnym przypadku porusza się on chaotycznie, wybierając losowo
punkty w aktualnym obszarze poszukiwań.

Podczas śledzenia agent organizuje przetarg na weryfikację czy jego rozpoznanie jest trafne. Jeśli weryfikacja zakończy się
sukcesem to kontynuuje on śledzenie, oraz zaczyna periodyczne informowanie agentów naziemnych o pozycji łosia. W przeciwnym 
przypadku powraca do patrolowania obszaru poszukiwań kontynuując w miejscu, w którym poprzednio zaprzestał.

\subsection{Weryfikacja}\label{subsection:weryfikacja}
Ponieważ możliwe jest, że agent powietrzny uzna inne zwierze za łosia, to aby upewnić się w trafności swojej oceny
potrzebne jest świadectwo innego agenta. Jako dodatkowe założenie przyjmuje się, że agent powietrzny 
poproszony o weryfikację bezbłędnej informacji.
\newline
\newline
Weryfikacja odbywa się według poniższego scenariusza, w którym agent:
\begin{enumerate}
 \item odnajduje agenta, którego uznaje ze łosia
 \item rozpoczyna śledzenie
 \item ogłasza przetarg, wysyłając do innych helikopterów wiadomość typu \newline \mas{call-for-proposal} z pozycją łosia do
 weryfikacji
 \item odbiera od pozostałych agentów wiadomości \mas{propose} z ich ceną lub\newline \mas{refuse}, gdy są zajęci
 \item wybiera najtańszą ofertę
 \item do wybranego agenta wysyła wiadomość \mas{accept-proposal} ze \newline zaktualizowaną pozycją łosia, a do reszty agentów wiadomość\newline typu \mas{refuse-proposal}
 \item oczekuje wiadomości typu \mas{confirm} lub \mas{disconfirm} informującej go\newline czy dane zwierze jest łosiem czy nie
\end{enumerate}

Jeśli agent, który wygrał przetarg wykluczy, że odnaleziono łosia, to śledzenie zostaje przerwane i organizator przetargu powraca do patrolowania.
Zaczyna się ono od miejsca omyłkowego rozpoznania. Jeśli, natomiast udało się potwierdzić, że rozpoznano łosia, to kontynuuje śledzenie 
i co 3000 jednostek czasu wysyła wiadomość do agentów naziemnych informującą o aktualnej pozycji uciekiniera.

W sytuacji, gdy w ramach przetargu nie uda się wybrać agenta mającego przeprowadzić weryfikację uznaje się, że cały proces zakończył
się niepowodzeniem i helikopter kontynuuje patrolowanie.
\newline

Na wiadomość typu \mas{call-for-proposal} agent odpowiada wiadomością typu \mas{propose} jeśli jest w trakcie
patrolowania lub typu \mas{refuse} z ceną równą odległości od zadanego punktu w przeciwnym wypadku.
Gdy helikopter wygra przetarg udaje się na wskazane miejsce. Jeśli w promieniu widoczności jest łoś odpowiada
wiadomością typu \mas{confirm} (weryfikowany agent jest łosiem), jeśli nie wysyła wiadomość
typu \mas{disconfirm}. Po zakończonym procesie wraca do miejsca, w którym skończył patrolowanie.

\chapter{Podsumowanie}

Zaimplementowany algorytm okazał się rozwiązaniem skutecznym. Za każdym uruchomieniem łosia udawało sie złapać i
wystrzelić doń jeden pocisk usypiający. Dzięki nadawaniu agentom w jednej grupie jednolitego koloru można łatwo analizować
algorytm podziału na grupy. Grupy aktywne, oznaczone kolorem białym, w większości przypadków były wybierane w rozsądny sposób.
Jednostki powietrzne w sposób efektywny wyszukiwały łosia i podawały jego pozycję agentom naziemnym.

Sporym problemem okazało się dobranie przedziałów czasowych, takich jak częstość rozpowszechniania informacji o pozycji łosia,
czy czas oczekiwania na odpowiedź na zapytanie lub żądanie.

W testach wydajnościowych wyszło na jaw, że ze względu na stosunkowo duże narzuty JADE-a przy
przekazywaniu komunikatów, system nie radzi sobie zbyt dobrze z dużą liczbą wiadomości, a co za tym idzie z dużą liczbą agentów.
Było to wyraźnie widoczne w algorytmie organizacji agentów naziemnych, który choć skuteczny, okazał się mało wydajny.
Przy dużej liczbie agentów tworzenie par i wybór par aktywnych nie udawało się ze względu na bardzo duże opóźnienia podczas
dostarczania wiadomości.
\newline
\newline
Stworzone narzędzie do wizualizacji działania systemów wieloagentowych okazało się wygodne i skuteczne. Możliwość robienia
własnych map, ich obracania, zbliżania i przesuwania, bardzo ułatwiło dokładną analizę ruchu agentów. Panel administracyjny
z prostym modelem interakcji z agentami daje stosunkowo duże możliwości i ułatwia badanie zaimplementowanego problemu MAS.
Wygodną funkcjonalnością okazała się możliwość zmiany upływu czasu w systemie, dzięki której można było dokładnie analizować
interesujące fazy algorytmu omijając pozostałe.

Dzięki stworzeniu wygodnego modelu świata i prostego sposobu tworzenia agentów, programista może skupić się jedynie na implementacji
samego problemu. Skraca to czas pracy wymagany do rozpoczęcia analizy.

\chapter{Dalszy rozwój platformy}

Spośród rzeczy, które mogą być rozwijane w przyszłości należy wymienić kilka szczególnie istotnych:

\begin{itemize}
 \item zwiększenie wydajności wymiany komunikatów
 \item rozszerzenie modelu świata - problem widoczności, prawdziwej grawitacji (obecnie agenci sami decydują czy mogą latać lub być pod ziemią)
 \item implementacja agentów wykorzystujących proste elementy sztucznej inteligencji
\end{itemize}

% \appendix
% \addcontentsline{toc}{chapter}{Dokumentacja javadoc}

\begin{thebibliography}{99}
\addcontentsline{toc}{chapter}{Bibliografia}
\bibitem{ALG1} L. Banachowski, K. Diks, W. Rytter, \textit{Algorytmy i struktury danych}, Wydawnictwa Naukowo-Techniczne (2001) 
\bibitem{JDB} F. Bellifemine, G. Caire, D. Greenwood, \textit{Developing Multi-Agent\newline Systems with JADE}, Willey (2007) 
\bibitem{ALG} T. H. Cormen, C. E. Leiserson, R. L. Rivest, Clifford Stein, \textit{Wprowadzenie do algorytmów}, Wydawnictwa Naukowo-Techniczne (2005)
\bibitem{BDK1} B. Dunin-Kęplicz, R. Verbrugge, \textit{Collective intentions}, Fundamenta Informaticae, vol.51, nr 3, IOS Press, 2002
\bibitem{BDK2} B. Dunin-Kęplicz, R. Verbrugge, \textit{Evolution of collective commitments during teamwork}, Fundamenta Informaticae, vol.56, nr 4, IOS Press, 2003
\bibitem{MOD} P. Kiciak, \textit{Podstawy modelowania krzywych i powierzchni}, Wydawnictwa Naukowo-Techniczne (2005)
\bibitem{JD} Tilab, \textit{Dokumentacja JADE} \vb{http://jade.tilab.com/doc/index.html}
\bibitem{JV} J. M. Vidal, \textit{Fundamentals of Multiagent Systems}, Nieopublikowano 
\bibitem{VV} G. Weiss, \textit{Multiagent Systems, A Modern Approach to Distributed \newline Artifitial Intelligence}, MIT Press (1999)
\bibitem{WD} M. Wooldridge, \textit{An Introduction to MultiAgent Systems}, Willey (2009)
\end{thebibliography}
\end{document}
